入门算法 - 质因数分解

内容同步于我的博客：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)的质因数。

算法描述

1. 枚举从2到sqrt(N)的所有质数fac，判断fac是否为N的因数；
   • 若fac为N的因数，则输出一次fac，并将N除以fac，得到新的N，重复此步骤直到fac不是N的因数为止
   • 若fac不是N的因数，则跳过
2. 在枚举结束后，若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;
}