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

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

对于整数 m，其质因数分解过程如下

步骤：

（1）生成 2~sqrt(m) 内的所有质数的质数表。（线性筛）（小于m的质数会存储在 prime[] 数组中，知道作用即可，改日分享）

（2）对于质数 pi，若m%pi = 0，while 循环执行，数组记录因子，记录因子个数加一，m = m/pi，反复执行1该步骤，直到 m%pi != 0。

（3）若 m = 1，则质因数分解结束。

代码实现：

#include<stdio.h>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("%d\n",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[] 数组中即可。