問題描述
- 任何一個合數(shù)都可以寫成幾個質(zhì)數(shù)相乘的形式，這幾個質(zhì)數(shù)叫做這個合數(shù)的質(zhì)因數(shù)衙熔。編程實(shí)現(xiàn)分解質(zhì)因數(shù)磅摹。
測試樣例
| 輸入 |
輸出 |
| 12 |
2 2 3 |
| 16 |
2 2 2 2 |
方法一：枚舉
方法二：Pollard Rho因數(shù)分解
- 1975年，John M. Pollard提出了第二種因數(shù)分解的方法罪郊，Pollard Rho快速因數(shù)分解。該算法時間復(fù)雜度為O（n^(1/4)）尚洽。
- 原理（以二重循環(huán)為例）從最小質(zhì)數(shù)i=2開始循環(huán)到n悔橄，（1）當(dāng)i可以整除n時，i為因數(shù)腺毫，執(zhí)行n=n/i癣疟，（2）繼續(xù)除i。當(dāng)i不能被整除時潮酒，執(zhí)行i++睛挚。繼續(xù)執(zhí)行（1）直到i=n
- 二重循環(huán)
//n為待分解的合數(shù)
for(i=2;i<=n;i++)
while(n!=i) {
if(n%i==0){
cout<<i<<' ';
n=n/i;
}
else
break;
}
cout<<n;
//調(diào)用方法recursion(m,2)
void recursion(int m, int n){
if (m >= n) {
while (m%n) n++;
m/=n;
recursion(m, n);
cout << n << endl;
}
}
參考文章
