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; } }