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

解题思路:

该问题基于算数基本定理

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

例如

36=2*2*2*3*3

20=2*2*5

由此定理可以发现，对于正整数  来说，它的任意一个因数  都是它质因数的乘积

所有因数即是它质因数乘积的各种组合

由此可以快速的分解出一个数  的所有因数

注意事项:

参考代码:

#include<iostream>

#include<cmath>

using namespace std;

typedef long long LL;

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

//由此可以发现，对于正整数N来说，它的任意一个因数T都是它质因数的乘积

LL n;

LL cnt;

int main()

{

cin>>n;

LL i; 

for(i=2;i<=sqrt(n)&&i>1;i++)

{

if(n%i==0) cnt++;

while(n%i==0) //去掉那些相同的质因子i 

{

n/=i;

}

} 

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

cout<<cnt<<endl;

}