质因数分解

· · 个人记录

题目链接： 蓝桥杯2022年第十三届省赛真题-质因数个数

题目描述：

给定正整数 n，请问有多少个质数是 n 的约数。

输入格式：

输入的第一行包含一个整数 n。

输出格式：

输出一个整数，表示 n 的质数约数个数。

样例输入：

396

样例输出：

3

提示：

396 有 2, 3, 11 三个质数约数。

对于 30% 的评测用例，1 ≤ n ≤ 10000。

对于 60% 的评测用例，1 ≤ n ≤ 109。

对于所有评测用例，1 ≤ n ≤ 1016。

思路：

对于任意一个正整数 ，可以将它分解成n个质因子的乘积

例如：

36=2*2*2*3*3

20=2*2*5

由此定理可以发现，对于正整数来说，它的任意一个因数都是它质因数的乘积，所有因数即是它质因数乘积的各种组合，由此可以快速的分解出一个数的所有因数

代码：

#include<iostream>
#include<cmath>

using namespace std;

typedef long long LL;

LL n;
LL cnt = 0;

int main() {
    cin >> n;

    if (n == 1) {
        cout << 0 << endl;
        return 0;
    }

    LL i; 
    for (i = 2; i <= sqrt(n) && n > 1; i++) {
        if (n % i == 0) cnt++;
        while (n % i == 0) {  // 去掉那些相同的质因子i 
            n /= i;
        }
    }

    if (i > 1) cnt++;  // 如果最后剩下的大于1，就加上余下的那个质因子 

    cout << cnt << endl;

    return 0; 
}