By

文章目录
  1. 1. 统计小于n的所有质数问题
    1. 1.1. 题目描述
    2. 1.2. 解法一
    3. 1.3. 解法二
    4. 1.4. 解法四

最近在刷LeetCode，对遇到的一些问题进行记录。

统计小于n的所有质数问题

题目描述

Description:
Count the number of prime numbers less than a non-negative number, n.
题目即为统计小于n的所有质数的数目；

解法一

目前最简单易懂的解法描述为：

质数不能被1和它本身之外的正整数整除，所以，如果要判断一个数x是不是质数只要看它是否能被2~sqrt(x)间的数整除即可。

解法的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int countPrimes(int n) {
    int i, count = 0;
    for (i = 2; i < n; i += 2) {  // 只考虑奇数
        if ((i%2==0) || (i%3==0) || (i%5==0) || (i%7==0))
            continue; 
        else if (isPrime(n) == 1) count++;
    }
    return count;
}

// 该函数判断是否是质数
int isPrime(int num) {
    int limit, i;
    if (num <= 1) return 0;
    if (num == 2 || num == 3) return 1;
    limit = sqrt(n) + 1;
    for (i = 2; i < limit; ++i) {
        if (num % i == 0) return 0;
    }
    return 1;
}

显然这种解法的复杂度为O（n^2），因此在提交的时候会直接Time Limit Exceeded。

解法二

仔细研究上面的算法可以发现如下优化:

合数可以分解成若干个质数，因此只要2~sqrt(n)间的质数不能整除n即可, 因此在下面的算法中我们会将找到的质数全部保存下来。

先看c代码：

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
int countPrimes(int n) {
    int count = 0;
    int i,j;
    int end = 0;
    // 首先动态申请数组空间用于保存质数
    int* primes = (int*)malloc(n*sizeof(int)); 
    int limit;
    if (n <= 2) return 0;
    primes[count++] = 2;  // 第一个质数明显是2，不用再判断
    for (i = 3; i < n; i++) {
        limit = sqrt(i);  //计算判断的终止点
        // 要判断i是不是质数，只需要判断2-sqrt(i)中的所有质数，
        // 因此下面的while语句即为找到prime数组中小于sqrt(i)
        // 的最大质数的下标
        while (primes[end] <= limit && end < count) end++;
        // 然后依次判断所有质数，如果整除说明不是质数
        // 否则将该数加入质数数组中；
        for (j = 0; j < end; j++) {
            if (i % primes[j] == 0) break;
        }
        if (j == end) primes[count++] = i;
    }
    free(primes);  // 记得释放动态空间
    return count;
}

上面的代码再次提交后会发现提交通过，运行时间为260ms，仍然还是较慢；

解法三

下面再次考虑新的解法。

质数就是只能位1和本身整除的数。因此如果我们将小于n的数中2,3,4，…n-1的倍数去除，那么剩下的自然就是质数。这就是筛选法。

更进一步的：

  1. 我们主要考虑2-（n/2+1）即可，显然大于等于(n/2+1)不可能被n整除；
  2. 主要考虑2-（n/2+1）的所有质数即可；

c代码如下：

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
int countPrimes(int n) {
    int count = 0;
    int i,j,limit;
    // 0-n 即为n+1,该数组用于存储是否是质数标志，
    // 因此pflags[i]代表i是否是质数
    char* pflags = (char*)malloc(n+1); 
    if (n <= 2) return 0;

    pflags[2] = 1;  // 2显然是质数
    for (i = 3; i < n; ++i) { //初始化数组
        pflags[i++] = 1;  // 所有的奇数初始为1，偶数为0
        pflags[i] = 0;
    }
    
    limit = n / 2 + 1; 
    // 下面的循环用于依次去掉3-limit的每个数的倍数，对于i， 
    // 如果i是合数，那么跳过3，因此只用考虑质数
    // 如果i是质数，那么从2×i开始，依次将小于n的i的倍数标为0
    // 此处使用加法代替乘法
    for (i = 3; i < limit; ++i) {
        if (0 == pflags[i]) continue;
        for (j = i+i; j < n; j += i) {
            pflags[j] = 0;
        }
    }
    
    for (i = 2; i < n; ++i) {
        if (1 == pflags[i]) count++;  // 遍历数组，统计质数数目
    }
    
    return count;
}

该方法提交成功，运行时间为96ms， 比解法2大大提升。

解法四

在discuss中，发现一个使用c写的运行28ms的代码如下：
也是使用筛选法，代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#define N 2000000
#define M 200000
class Solution {
public:
    bool visit[N] = {};
    int p[M] = {};
    int countPrimes(int n) {
        int res = 0;
        for(int i = 3; i < n; i+=2) {
            if(!visit[i]) {
                p[res++] = i;
            }
            for(int j = 0; j < res && i*p[j] < n; j++) {
                visit[i*p[j]] = true;
                if(i % p[j] == 0) {
                    break;
                }
            }
        }
        return res+(n>2?1:0);
    }
};

转载请标明文章出处。本文内容为实践后的原创整理，如果侵犯了您的版权，请联系我进行删除，邮件：yanhealth@163.com

文章目录
  1. 1. 统计小于n的所有质数问题
    1. 1.1. 题目描述
    2. 1.2. 解法一
    3. 1.3. 解法二
    4. 1.4. 解法四