质因数个数（第十三届蓝桥杯）

题目

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

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

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

数据范围
对于 $30$%的评测用例,$1\le n\le 10000。$
对于 $60$% 的评测用例，$1\le n\le 109。$
对于所有评测用例，$1\le n\le 10^{16}。$

输入样例：

396

输出样例：

3

样例解释

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

代码（python版本）

n=int(input())
i=2
res=0
while i<n//i:
    if n%i==0:
        res+=1
        while  n%i==0:
            n//=i
    i+=1
if n>1:
    res+=1
print(res)

代码 （cpp版本）

#include<iostream>
using namespace std;
typedef long long LL;
LL n;
int main()
{
    scanf("%lld", &n);
    LL res = 0;
    for(LL i = 2; i <= n / i; i ++)
        if(n % i == 0)
        {
            res ++;
            while(n % i == 0) n /= i;
        }
    if(n > 1) res ++;
    printf("%lld", res);
    return 0;
}

思路：

本题可以算是一个板子题，但是得注意题目的意思，题目是寻找质因数的个数，比如案例中，396可以被6整除，但是为什么不算6呢？因为6可以分为2*3，所以本质上来说相当于396是被2或者3整除的。
众所周知，$n$的质因子应该在$\sqrt{n}$中找，大于$\sqrt{n}$中是没有$n$的质因子的，至于为什么这里就不讲了。那么我们只需要定义一个$i$，从$i$到$\sqrt{n}$中遍历就行，但是数据的大小是$10^{16}$,开根号之后复杂度是$10^8$,还是跑不掉，那怎么办呢？
那接下来我们来看看如果按照上面的思路来进行，$396$是如何被分解的，首先$396/2=198$,然后$198/3=66$,接着66不能被4和5整除，但是可以被6整除，$66/6=11$，接下来就是不断的循环，一直到11,也就是$11/11=1$,然后一直循环到$\sqrt{396}为止$，那么我们看到这个过程，我们可不可以想一想能否优化一下这个思路呢？首先就是循环中的6就是上面我所说的“6可以分为2*3”，那么我们只需要让他在除2的时候除两次就好了，同理除3的时候也除两次，然后等循环到n=1的时候我们就可以那么我们可以将分解重新变一下。
首先$396/2=198$，然后判断还可不可以继续分解，也就是判断198%2是否为0，很明显为0，那么我们继续首先$198/2=99$,这时候99不能被2整除了，接下来就到了3，$99/3=33$,$33/3=11$,然后就是循环到11之后，就可以退出了。
这里还有个小细节是什么呢，就是当n是质数的时候，比如n=7的时候，这时候循环只会到$\sqrt{7}$（实际到2，因为是向下取整）就停止了，但是7可以被它自己整除，所以当循环结束之后，我们还需要判断n是否大于1，如果$n>1$，那么我们需要在答案上+1，这样才是最终的答案。

原文地址：https://blog.csdn.net/m0_70182646/article/details/135774470

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！