质因数的个数 (分解质因数)

链接：https://www.nowcoder.com/questionTerminal/20426b85f7fc4ba8b0844cc04807fbd9?f=discussion
来源：牛客网

[编程题]质因数的个数

热度指数：20444 时间限制：1秒空间限制：65536K

求正整数N(N>1)的质因数的个数。相同的质因数需要重复计算。如120=2*2*2*3*5，共有5个质因数。

输入描述:

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

输出描述:

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

示例1

输入

输出

思路

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 }