九度OJ-1207：质因数的个数

　　此题的关键代码是37-39行：

else if ( prime[index]>(int)(sqrt(n))+1 ){ count++; break;必须在此prime[index]无法整除n时加一条这个判断，不仅因为这样做能够减少计算量，还因为输入n的上限是十亿，sqrt(10 0000 0000)尚能在int的范围之内不会溢出，不这么处理就溢出了。

题目地址：点击打开链接 题目描述： 求正整数N(N>1)的质因数的个数。 相同的质因数需要重复计算。如120=2*2*2*3*5，共有5个质因数。 输入：

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

输出：

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

样例输入： 120 样例输出： 5 提示：

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

来源： 2007年清华大学计算机研究生机试真题 答疑： 解题遇到问题?分享解题心得?讨论本题请访问： http://t.jobdu.com/thread-7930-1-1.html #include <iostream> #include <cmath> using namespace std; int main(){ int n; bool isPrime[30000]; int prime[5000]; int primeSize; int count; //preprocess primeSize=0; for (int i=2;i<30000;i++){ isPrime[i]=true; } for (int i=2;i<30000;i++){ if (isPrime[i]==true){ prime[primeSize]=i; primeSize++; for (int j=2*i;j<30000;j+=i){ isPrime[j]=false; } } } while (cin>>n){ //initiate count=0; int index=0; //process while (index<primeSize){ if (n==1) break; else if (n%prime[index]==0){ n/=prime[index]; count++; } else if ( prime[index]>(int)(sqrt(n))+1 ){ count++; break; } else index++; } //output cout<<count<<endl; } return true; }