内容同步于我的博客：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;
}
