質(zhì)因數(shù)分解的最簡單方法（最好理解的方法）

對(duì)于整數(shù) m，其質(zhì)因數(shù)分解過程如下
步驟：
（1）生成 2~sqrt(m) 內(nèi)的所有質(zhì)數(shù)的質(zhì)數(shù)表。（線性篩）（小于m的質(zhì)數(shù)會(huì)存儲(chǔ)在 prime[] 數(shù)組中，知道作用即可，改日分享）
（2）對(duì)于質(zhì)數(shù) p_i，若m%p_i = 0，while 循環(huán)執(zhí)行，數(shù)組記錄因子，記錄因子個(gè)數(shù)加一，m = m/p_i，反復(fù)執(zhí)行1該步驟，直到 m%p_i != 0。
（3）若 m = 1，則質(zhì)因數(shù)分解結(jié)束。

代碼實(shí)現(xiàn)：

#include<stdio.h> int a[100010];//存儲(chǔ)質(zhì)因數(shù) int s[100010] = {0};//存儲(chǔ)質(zhì)因數(shù)的個(gè)數(shù) 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 的質(zhì)數(shù)的個(gè)數(shù) } int fenjie(int m) {int num = 0; //存儲(chǔ)質(zhì)因數(shù)的個(gè)數(shù) int cnt = Prime(m);//求小于 m 的素?cái)?shù)，存到數(shù)組 prime[] 中 for(int i = 0;i < cnt;i++){if(m%prime[i] == 0){ //如果能除盡while(m%prime[i] == 0){ //能除盡就一直除a[num] = prime[i]; //先存儲(chǔ)s[num]++; //計(jì)數(shù)再++m /= prime[i];}num++;}if(m == 1) break; //除完到 1 結(jié)束 }if(m != 1){ //當(dāng) m 為質(zhì)數(shù)的時(shí)候 a[num] = m;s[num] = 1;}return num; //返回所有質(zhì)因數(shù)的個(gè)數(shù) } 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; }

這里可能還有求質(zhì)數(shù)的方法看不懂，改日博客分享，知道意思就是將所有的質(zhì)數(shù)存儲(chǔ)在 prime[] 數(shù)組中即可。

總結(jié)

以上是生活随笔為你收集整理的数论-质因数分解（最基础方法）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。