题解 | #质因数的个数#

#include <iostream>
#include<cstring>
#include<cmath>
using namespace std;
#define maxn 100000
//10^9*4B约为4GB了
int a[maxn];
void isprime()
{
    //筛法求素数
    for(int i=2;i<maxn;i++)a[i]=1;
    for(int i=2;i<maxn;i++)
    {
        if(a[i]==1)
        {
            for(int j=i*2;j<maxn;j+=i)a[j]=0;
        }
    }
}
int main() {
    int x;
    isprime();
    //for(int i=0;i<10;i++)cout<<a[i]<<" ";
    while (cin >> x) 
    { 
       int count=0;
       int n=sqrt(x);
       int i=2;
       //相同质因数需要重复计算
       for(;i<=n&&x!=1;i++)
       {
        if(a[i]==1)
        {
            //问题在于：如果3*5*大素数,检索空间sqrt(x)内找不到
            //说明一定还有一个大素数
            while(x%i==0)
            {x=x/i;count++;
            //cout<<"质数:"<<i<<endl;
            }
        }
       }
       if(i==n+1)count++;
       cout<<count<<endl;
    }
}
// 64 位输出请用 printf("%lld")