摘要：
首先，非质数有两种情况：1.所有质数都小于或等于sqrt（n）2.只有一个质数大于sqrt（n），而其他质数小于sqrt（m）。如果有一个以上的素因子大于sqrt（n），则这些因子的乘积……以下代码在此使用结构。当然，也可以使用数组结构因子｛intx；//记录素因子intcnt；//素因子的数量｝fac[10]；2 3 5 7
先上原理
对于一个非素数来说有两种情况
1，所有质因子小于等于sqrt（n）
2，只存在一个大于sqrt（n）的质因子，其他质因子都小于sqrt（n）
至于证明，可以用反证法。
若是有多余一个大于sqrt（n）的质因子，这些因子的乘积.....
下面上代码
这里借助一个结构体，当然你也可以用数组
struct factor { int x;//记录素因子 int cnt;//素因子的个数 }fac[10];
2 3 5 7 11 13 17 19 23 29
以上10个素数的乘积已经超过了int的表示范围
故而结构体数组只开了10个
int prime_num;//质因子的个数 void prime_fac(int n) { for(int i=0;i<=sqrt(n);i++) { if(n%prime[i]==0) { fac[prime_num].x=prime[i]; while(n%prime[i]==0) { fac[prime_num].cnt++; n=n/prime[i]; } prime_num++; } } if(n!=1) { fac[prime_num].x=n; fac[prime_num].cnt=1; prime_num++; } }
该函数执行结束，fac结构体数组中就是质因子的分解结果