[数据结构与算法]基础练习 分解质因数

• 问题描述

基础练习 分解质因数

Description

求出区间[a,b]中所有整数的质因数分解。2<= a,b <=10000

Input

输入描述:

输入两个整数a，b。 2<= a,b <=10000

输入样例:

3 10

Output

输出描述:

每行输出一个数的分解，形如k=a1*a2*a3...(a1<=a2<=a3...，k也是从小到大的)(具体可看样例)

输出样例:

3=3

4=2*2

5=5

6=2*3

7=7

8=2*2*2

9=3*3

10=2*5

题目来源：OnlineJudge

• 解题分析

?题目要求分解成质因数形式，其实就是将一个数n通过除法逐步分解，除数从2开始遍历到n。如果可以整除，那么除数就是一个质因数，下一次以所得商作为要分解的数据进行重复上面分解过程直到最终的商为0结束；如果除数遍历n仍未出现可以整除n的除数，那n就是最后一个质因数。但是这里我们要思考一个问题，每一次除数都是从2开始到n结束，且n在此过程中可能会发生变换，怎样设计这里的算法呢？

首先，这里我们知道应该有两个循环，一个判断n是否为0；一个对除数从2到n进行遍历，所以有以下算法：

int main()
{
	int n = 100;
	int i = 0;
	printf("%d=", n);
	while (i!=n)
	{
		for (i = 2; i < n; i++)
		{
			if (n % i == 0)
			{
				printf("%d*", i);
				n /= i;
				break;
			}
		}
	}
	printf("%d\n", n);
	//输出结果：100=2*2*5*5
	return 0;
}

该算法中，while循环控制分解条件，当i！=n时继续n进行分解处理，直到i==n结束。这个还是很好理解的，实现了每次判断除数都从2到n进行遍历，也实现了分解一次后对n进行更新。但该算法仍存在效率的问题，我们不妨模拟一下上述分解100的整个过程，如下所示：

//开始：n=100，i=0，输出100=，进入while循环
//		i=2，100%2==0，输出2*
//		执行n/=i，更新n为50，即下一次分解的数据变成50
//		跳出for循环
//第二次while循环：n=50
//		i=2,50%2==0，输出2*
//		执行n/=i，更新n为25，即下一次分解的数据变成25
//		跳出for循环
//第三次while循环：n=25
//		i=2,25%2！=0
//		i开始遍历2到小于n之间的数，直到出现n%==0
//		当i遍历到i==5时，25%5==0，输出5*
//		执行n/=i，更新n为5，即下一次分解的数据变成5
//		跳出for循环
//第四次while循环：n=5（显然此时5是一个质数，不可再分解）
//		i=2,5%2！=0
//		i开始遍历2到小于n之间的数，直到出现n==i
//		当n==i时跳出for循环，同时结束while循环
//		执行最后语句，输出5
//整个输出结果：100=2*2*5*5

从上面过程中，我们可以分析，每用n/=i更新一次n后，下一次除数都从2至n-1开始遍历，但我们直到，更新后的n是不可能再被小于上一个输出的i的数整除的，这里造成了资源浪费，下面将代码优化，提高效率，如下：

void Decompose(int n)
{
	//整个过程，n如果不是质数，n会一直变化
	int i = 0;
	printf("%d=", n);//按照题目要求的输出形式打印每一次要处理的数
	for (i = 2; i <= n; i++)//这里循环条件和随着下面分解会发生相应改变，但最终循环结束时都是 n=i+1;值得注意的是，这里的可以省去=，即for (i = 2; i <= n; i++)，但是这样写不方便大家理解下面的while循环判断条件
	{
		while (n != i)//i<n进入该循环，n=i时跳出该循环
		{
			if (n % i == 0)//如果n能被i整除，那可以分解出质因数i
			{
				printf("%d*", i);
				n /= i;//分解后对n进行处理，使下一次处理的对象变为n/i
			}
			else//n不能被i整除，跳出while循环，i自增1后进行下一次分解判断
			{
				break;
			}
		}
	}
	printf("%d\n", n);//来到这里只有一种情况，就是上面while循环条件中n=i，但由于结束for循环后i自增1，所以这里用n打印
}

这里换了一种思路，只遍历一次2到n的数，在for循环里面利用while循环分解n（当i<n时进行判断分解）。如果i<n,进入while判断分解，如果n%i==0，输出i*，更新n=n/i，继续进行判断分解，除数仍是i；如果n%i!=0,break跳出while循环，i自增1，继续进行上述操作。我们看到n的改变，也会影响外重for循环判断条件的改变，但最终结束情况其实就是n已经是一个质数，不能分解，最后输出即可。最终的情况，如果以while来判断，当i自增到i==n时，并不进入while循环，也就是不执行打印语句和更改n的语句，n不再改变，跳过for循环后，i自增1；这时，在for循环判断条件中i>n,不满足条件，跳出for循环，意味着分解过程结束，n是一个质数，不能再分解，输出最后的n即可。

分析到这里，解决本题的核心算法已经基本理清。

• 问题总结

1.首先从一个最小的质数i=2开始，最小的质数为2
2.如果这个质因数i等于n那么分解过程就结束了
3.如果i不等于n,但是n可以被i整除，那么输出这个i，并用n/i（n除以i）作为n的新值，并重复步骤2（用循环），i仍作为除数
4.如果n不能被k整除，那么是i=i+1; 重复执行第2、3步
注意：应深入理解2,3,4的循环步骤，可举一个合适的例子在纸上模拟一遍
?

• AC代码

#pragma warning(disable:4996)
#pragma warning(disable:6031)
#pragma warning(disable:6054)
#pragma warning(disable:6385)

#include<stdio.h>

void Decompose(int n);//定义一个可以一个整数（n>=2）进行分解质因数操作的函数

int main()
{
	int a = 0;//左端点
	int b = 0;//右端点
	int i = 0;//表示区间[a,b]中的整数
	while (scanf("%d %d", &a, &b) != EOF)
	{
		for (i = a; i <= b; i++)//遍历a和b之间的所有整数，逐个分解
		{
			//下面函数对i进行分解质因数处理
			Decompose(i);
		}
	}

	return 0;
}

void Decompose(int n)
{
	//整个过程，n如果不是质数，n会一直变化
	int i = 0;
	printf("%d=", n);//按照题目要求的输出形式打印每一次要处理的数
	for (i = 2; i <= n; i++)//这里循环条件和随着下面分解会发生相应改变，但最终循环结束时都是 n=i+1;值得注意的是，这里的可以省去=，即for (i = 2; i <= n; i++)，但是这样写不方便大家理解下面的while循环判断条件
	{
		while (n != i)//i<n进入该循环，n=i时跳出该循环
		{
			if (n % i == 0)//如果n能被i整除，那可以分解出质因数i
			{
				printf("%d*", i);
				n /= i;//分解后对n进行处理，使下一次处理的对象变为n/i
			}
			else//n不能被i整除，跳出while循环，i自增1后进行下一次分解判断
			{
				break;
			}
		}
	}
	printf("%d\n", n);//来到这里只有一种情况，就是上面while循环条件中n=i，但由于结束for循环后i自增1，所以这里用n打印
}

• 后记

?本篇blog主要是我对C语言OJ作业的题目总结，后续还会继续更新其他题目。如果篇目中有解释得不够清楚的地方或者读者有更好的算法，我们可以在评论区交流，让我们继续完善这篇blog，同时也可以帮助我下次写出更好的blog。