来源：牛客网
[编程题]质因数的个数
热度指数：20444 时间限制：1秒 空间限制：65536K
求正整数N(N>1)的质因数的个数。 相同的质因数需要重复计算。如120=2*2*2*3*5，共有5个质因数。
输入描述:
可能有多组测试数据，每组测试数据的输入是一个正整数N，(1<N<10^9)。输出描述:
对于每组数据，输出N的质因数的个数。示例1输入
120输出
5
思路
1）题目需要多组测试用例，我的第一个想法是没能每个测试用例都去判断质数，所以可以使用打表法，把100000以内的质数标记出来
2）因为c 中的数组不能太大（同时也是考虑到题目有内存要求），标记的质数表不能全部包含所有可能的输入数据的质因数，这里就有一个小技巧：如果输入的数据n最后剩余不为1，则表示还存在一个大于质数表内的质数
1 #include<iostream> 2 #include<string> 3 #include<cmath> 4 #include<algorithm> 5 6 using namespace std; 7 8 bool mark[10000]; 9 int prime[10000];10 int primeSize = 0;11 12 void init()13 {14 mark[1] = false;15 for(int i = 2; i < 10000; i)16 mark[i] = true;17 for(int i = 2; i < 10000; i)18 {19 if(mark[i] == true)20 {21 prime[primeSize ] = i;22 for(int j = i*i; j < 10000; j = i)23 mark[j] = false; 24 }25 }26 }27 28 int main()29 {30 init();31 int num;32 while(cin >> num)33 {34 int ans = 0;35 for(int i = 0; i < primeSize; i)36 {37 if(num == 1)38 break;39 if(num % prime[i] == 0)40 {41 num /= prime[i];42 ans ;43 i--;44 }45 }46 if(num != 1) // 若测试完2到10000内所有素因数, num仍未被分解至1, 则剩余的因数一定是一个大于10000的素因数47 ans ;48 cout << ans << endl;49 }50 51 return 0;52 }思路升级
其实不需要再循环里判断i是为为质数，如果i是合数，则一定不会被整除：那前面的质数一定已经合数中包含的质数被整除过了
1 #include <iostream> 2 #include <math.h> 3 using namespace std; 4 int main() 5 { 6 int n; 7 while(cin>>n) 8 { 9 int i,count=0;10 for(i=2; i<=sqrt(n); i )11 {12 while(n%i==0)13 {14 count ;15 n/=i;16 }17 }18 if(n>1)19 count ;20 cout<<count<<endl;21 }22 return 0;23 }
