Catch Your Dream

0%

NowCoder-质因数个数

Posted on Edited on In Disqus:
Symbols count in article: 1.1k Reading time ≈ 3 mins.

Problem

补之前的

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

Examples:

Input:
可能有多组测试数据，每组测试数据的输入是一个正整数N，(1<N<10^9)。
Output:
对于每组数据，输出N的质因数的个数。

Solutions

  • 先计算素数，然后找因数

C++ Codes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/*
 * 素数筛
 * 计算处sqrt(n)以内的素数
 * 最后的部分是一个比sqrt(n)大的素数，个数加1即可
 */
#include<iostream>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;

#define MAXN 100000
int prime[MAXN];
bool valid[MAXN];

//素数筛，返回1-num以内素数个数并存在pr数组内
int getPrime(int *pr, int num){
  int res = 0;
  memset(valid, true, sizeof(valid));
  for(int i=2;i<=num;i++){
    if(valid[i]) pr[res++]=i;

    for(int j=0;j<res;j++){
      //更新所有素数和当前数乘积为false
      if(pr[j]*i>num)break;
      valid[pr[j]*i]=false;

      //如果是已知素数的倍数，就break；
      if(i%pr[j]==0) break;
    }
  }
  return res;
}

int main(){
  int sumCnt = getPrime(prime, MAXN);
  int n;
  while(cin>>n){
    int cnt = 0;
    int sq = sqrt(n);
    for(int i=0;i<sumCnt;i++){
      if(prime[i]>sq) break;
      while(n%prime[i]==0){
        cnt++;
        n/=prime[i];
      }
    }
    if(n>1) cnt++;
    cout<<cnt<<endl;
  }

}

总结

  • 素数筛还是要会的，几种筛法
disqus gitalk