数论-质因数分解（最基础方法）

质因数分解的最简单方法（最好理解的方法）

对于整数 m，其质因数分解过程如下
步骤：
（1）生成 2~sqrt(m) 内的所有质数的质数表。（线性筛）（小于m的质数会存储在 prime[] 数组中，知道作用即可，改日分享）
（2）对于质数 p_i，若m%p_i = 0，while 循环执行，数组记录因子，记录因子个数加一，m = m/p_i，反复执行1该步骤，直到 m%p_i != 0。
（3）若 m = 1，则质因数分解结束。

代码实现：

#include
int a[100010];//存储质因数 
int s[100010] = {0};//存储质因数的个数 

int prime[10000005],judge[10000005];//把可以求的范围开到最大 
int Prime(int m)//线性筛
{
	int num = 0;
	for(int i = 2;i < m;i++){
		if(!judge[i]) prime[num++] = i;
		for(int j = 0;j < num && prime[j]*i < m;j++){
			judge[i*prime[j]] = 1;
			if(i%prime[j] == 0) break;
		}
	}
//	for(int i = 0;i < num;i++) printf("%dn",prime[i]);
	return num;//返回小于 m 的质数的个数
}
int fenjie(int m)
{
	int num = 0;	//存储质因数的个数 
	int cnt = Prime(m);//求小于 m 的素数，存到数组 prime[] 中 
	for(int i = 0;i < cnt;i++){
		if(m%prime[i] == 0){	//如果能除尽
			while(m%prime[i] == 0){	//能除尽就一直除
				a[num] = prime[i];	//先存储
				s[num]++;	//计数再++
				m /= prime[i];
			}
			num++;
		}
		if(m == 1) break;	//除完到 1 结束 
	}
	if(m != 1){		//当 m 为质数的时候 
		a[num] = m;
		s[num] = 1;
	}
	return num;	//返回所有质因数的个数 
}
int main()
{
	int m;
	scanf("%d",&m);
	int cnt = fenjie(m);
	for(int i = 0;i < cnt;i++){
		if(i == 0) printf("%d = ",m);
		if(i != 0) printf(" * ");
		printf("%d",a[i]);
		printf("^%d",s[i]);
	}	
	return 0;
}

这里可能还有求质数的方法看不懂，改日博客分享，知道意思就是将所有的质数存储在 prime[] 数组中即可。