题目1207：质因数的个数
时间限制：1 秒
内存限制：32 兆
特殊判题：否
提交：9892
解决：3202
-
题目描述：
-
求正整数N(N>1)的质因数的个数。相同的质因数需要重复计算。如120=2*2*2*3*5，共有5个质因数。
-
输入：
-
可能有多组测试数据，每组测试数据的输入是一个正整数N，(1<N<10^9)。
-
输出：
-
对于每组数据，输出N的质因数的个数。
-
样例输入：
-
120
-
样例输出：
-
5
-
提示：
-
注意：1不是N的质因数；若N为质数，N是N的质因数。
-
来源：
- 2007年清华大学计算机研究生机试真题
-
-
//1.先保存一定量的素数，用于遍历。本题输入的正整数最大为10^9，所以素数范围控制在 sqrt(10^9)==以内即可 //sqrt(10^9)=31622.7 此处选择 筛10 0000 以前的所有素数。 //2.用输入数据挨个去除素数，如果能除尽，说明该素数的输入数据的质因数， //并进一步记录除尽该质因数的个数，直到除不尽为止。 //如果此时输入数据为 1 ，结束遍历素数循环。如果不为 1 ，则继续循环。 //跳出循环后，仍然可能存在输入数据并非为 1 的情况，此时该输入数据一定 //包含一个大于sqrt(n)的质因数，并且该质因数的次数为 1 #include <cstdio> #include <cmath> bool num[100001]; int prime[100001]; int primesize; void init(){primesize=0;for(int i=0;i<100001;i++){num[i]=false;}for(int i=2;i<100001;i++){if(num[i]==true)continue;prime[primesize++]=i;for(int j=i+i;j<100001;j+=i){num[j]=true;}} }int main(){init();int n;while(scanf("%d",&n)!=EOF){int ansPrime[30];//保存质因数int ansSize=0;//保存质因数的个数，不要忘了将其初始化为零int ansNum[30];//保存质因数的次数for(int i=0;i<primesize;i++){if(n%prime[i]==0){//prime【i】 是该数的质因数ansPrime[ansSize]=prime[i];ansNum[ansSize]=0; //初始化很重要while(n%prime[i]==0){ansNum[ansSize]++;n=n/prime[i];}ansSize++;}if(n==1) break;}if(n!=1){ansPrime[ansSize]=n;ansNum[ansSize]=1;ansSize++;}int ans=0;for(int i=0;i<ansSize;i++){ans+=ansNum[i];}printf("%d\n",ans);}return 0; }