內容同步于我的博客：https://blog.bigrats.net/archives/basic-alg-prime-factors.html
題目描述
輸入一個正整數商架，按照從小到大的順序輸出它的所有質因數
輸入描述
輸入一個long類型的整數
輸出描述
按照從小到大的順序輸出它的所有質數的因子细卧，以空格隔開档礁。最后一個數后面也要有空格对雪。
示例
Input:
180
Output:
2 2 3 3 5
問題分析
我們首先應該知道帜乞，對一個正整數N來說虱朵，如果其存在除1和本身外的其他因數余境，那么必然會在N的平方根左右成對出現。根據這個原理毁渗，我們可以分析得出践磅，N最多只存在一個大于sqrt(N)的質因數。
算法描述
- 枚舉從2到sqrt(N)的所有質數fac灸异，判斷fac是否為N的因數府适；
- 若fac為N的因數，則輸出一次fac肺樟，并將N除以fac檐春，得到新的N，重復此步驟直到fac不是N的因數為止
- 若fac不是N的因數么伯，則跳過
- 在枚舉結束后疟暖，若N依然不為1，則說明原N有且僅有一個大于sqrt(原N)的質因數田柔，直接輸出此數即可俐巴。
代碼
#include <cstdio>
#include <cmath>
using namespace std;
bool isPrime(int num) {
int sqr = (int)sqrt(num);
if(num == 1) return false;
for(int i = 2; i <= sqr; i++) {
if(num % i == 0) return false;
}
return true;
}
int main(int args, char* argv[]) {
long inpnum;
while(scanf("%ld", &inpnum) != EOF) {
long uplimit = (long)sqrt(inpnum);
for(long fac = 2; fac <= uplimit; fac++) {
if(isPrime(fac)) {
while(inpnum % fac == 0) {
printf("%ld ", fac);
inpnum /= fac;
}
}
}
if(inpnum != 1) {
printf("%ld ", inpnum);
}
printf("\n");
}
return 0;
}
