题解 | 质因数的个数

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn =1e6;
bool flag[maxn];
int pri[maxn];

int main() {
    int n;
    cin>>n;
    int ans=0;
    int cnt =0;
    for(int i=2;i<=sqrt(n);i++) //欧拉筛
    {
        if(!flag[i])pri[cnt++] = i;
        for(int j =0;j<cnt;j++)
        {
            if(pri[j]*i>sqrt(n))break;
            flag[pri[j]*i]=1;
            if(i%pri[j]==0)
            {
                break;
            }
        }
    }
 //   while(n!=1)
    {
        for(int i = 0;i<cnt;i++)
        {
            while(n%pri[i]==0)
            {
                ans++;
                n/=pri[i];
         //     break;
            }
        }
    }
    if(n!=1)ans++;
 //   cout<<n<<endl;
    cout<<ans<<endl;
    
    
}
// 64 位输出请用 printf("%lld")