ACWing 3380. 质因数的个数

求正整数 N（N>1）的质因数的个数。

相同的质因数需要重复计算。

如 120=2×2×2×3×5，共有 5 个质因数。

输入格式

输入可能包含多组测试数据。

每组数据占一行，包含一个正整数 N。

输出格式

对于每组输入，输出一行结果表示 N 的质因数的个数。

数据范围

1<N<10^9
每个输入最多包含 100 组测试数据。

输入样例：

120

输出样例：

5

暴力解法

#include<iostream>
#include<math.h>

using namespace std;

int main()
{ int n=0;
while(cin>>n)
{ int count=0;
for(int i=2;i<=n;i++)
{
if(n%i==0)//i是最小的质因数
{
count++;
n=n/i;
i=1;
}

}
cout<<count<<endl;
}
}
但是在输入数据过大时会超时。如果想优化，只需要计算到i<=sqrt(n)即可。但是如果这样则需要额外进行一次判定，即当i=n本身时，for循环中的判定是判定不到的

如果根号n以内的数都不再存在n的质因数，那就只剩n本身能作为n的质因数了

所以我们无需经历从根号n到n的这一段循环，只需在i大于等于根号n以后单独进行一次判定

如果n>1 (n=1说明n已经被分解完毕) 则count++;

int main()
{ int n=0;
while(cin>>n)
{ int count=0;
for(int i=2;i<=sqrt(n);i++)
{
if(n%i==0)//i是最小的质因数
{
count++;
n=n/i;
i=1;
}

}if(n>1) count++;
cout<<count<<endl;
}
}

除此之外

for(int i=2;i<=n;i++)
{
if(n%i==0)//i是最小的质因数
{
count++;
n=n/i;
i=1;
}

}

每次查到n的最小质因数i以后，都需要重新从i=2开始查，在if结束时额外设置一个i=1看起来太蠢了

可以直接将if改为while，如果当前的数还能被i整除，就继续除以i，如果当前的数无法再被i整除，那以后这个数也不可能再被i整除，使用while直接将n的所有为i的质因数分出来后再进入下一个。

for(int i=2;i<=n;i++)
{
while(n%i==0)//i是最小的质因数
{
count++;
n=n/i;
}

}