题解 | #质因数的个数#

#include <iostream>
#include <cmath>
using namespace std;


const int N=sqrt(1e+9);//N=31622
bool prime[31623];

void Initial()
{
    for(int i=0;i<=N;i++)
    {
        prime[i]=true;
    }
    prime[0]=false;
    prime[1]=false;
    for(int i=2;i<=N;i++)
    {
        if(prime[i]==false)continue;
        for(int j=i*2;j<=N;j+=i)
        prime[j]=false;
    }
}

int main() {
    Initial();//本题也可以不用求prime数组
    int n;
    while (cin >> n) { 
        int bound=sqrt(n);
        int count=0;

 /*       for(int i=2;(i<=bound)&&(prime[i]==1);i++)//不能这样，一旦prime[4]不满足条件之后就会跳出循环
        {
            while(n%i==0)
            {
                count++;
                n/=i;
            }

        }
*/         
            for(int i=2;i<=bound;i++)
        {
            if(prime[i]==false)continue;//其实本题也用不到这句话
            while(n%i==0)
            {
                count++;
                n/=i;
            }

        }
        if(n>1)count++;

        cout<<count<<endl;
    }
}