1.先用素数筛子求出sqrt(1e9)+1内的所有的素数(取根号是因为一个数n所有质因数中只有一个大于sqrt平方的)。
2.依次对给定的数n除以他的质因数,如果除到了1,说明除尽了,如果没除到1,就将素数筛子里的数向后移一位判断。
3.如果最后都判断完了,n仍!=1,说明存在一个大于他的根号的因数,那么加一即可。

#include<iostream>
#include<vector>
#include<math.h>
using namespace std;
const int maxn=sqrt(1e9)+1;
int main(){
    vector<int> vec;
    bool isprime[maxn];
    for(int i=0;i<maxn;i++){
        isprime[i]=true;
    }isprime[0]=isprime[1]=false;
    for(int i=2;i<maxn;i++){
        if(!isprime[i]){
            continue;
        }vec.push_back(i);
        for(int j=i*i;j<maxn;j+=i){
            isprime[j]=false;
        }
    }
    int sum=0,n;
    while(cin>>n){
        int i=0;
        while(n!=1){
            if(i==vec.size())break;
            if(n%vec[i]==0){
                n/=vec[i];
                sum++;
            }else i++;
        }if(n!=1)sum++;
        cout<<sum<<endl;
    }

}