问题 C: 质因数的个数

1947: 质因数的个数

时间限制: 1 Sec  内存限制: 32 MB
提交: 245  解决: 114
[提交][状态][讨论版][命题人:外部导入]

题目描述

求正整数N(N>1)的质因数的个数。

相同的质因数需要重复计算。如120=2*2*2*3*5，共有5个质因数。

输入

可能有多组测试数据，每组测试数据的输入是一个正整数N，(1<N<10^9)。

输出

对于每组数据，输出N的质因数的个数。

样例输入

120
200

样例输出

5
5

提示

注意1不是N的质因数；若N为质数，N是N的质因数。

#include<bits/stdc++.h>

using namespace std;


//取N=1e9  是因为n只可能有一个质因数大于le9 或者都小于
const int N=1e5;
int prime[N];

int vis[N];
int cnt=0;
void find_prime()
{
    fill(vis,vis+N,false);
    for(int i=2;i<N;i++){
        if(!vis[i]){
          prime[cnt++]=i;
          for(int j=i+i;j<N;j+=i){
            vis[j]=true;
          }
        }

    }

}
int main()
{
    find_prime();
    int n;
    while(scanf("%d",&n)==1){
        int num=0;
        for(int i=0;i<cnt;i++){
           while(n%prime[i]==0){
                num++;
                n/=prime[i];
           }
           if(n==1) break;
        }
        if(n!=1) num++;//这里是判断大于 sqrt(1e9)的数
        printf("%d
",num);
    }

    return 0;
}