简单介绍素数判断及其分布规律。

1. Description

题目链接 Count the number of prime numbers less than a non-negative number n.

Example:

1
2
3

Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

2. 思路分析

使用埃拉托斯特尼筛选法，获取素数序列，从而得到小于 n 的素数个数。

埃拉托斯特尼筛选法，简称埃氏筛或爱氏筛，是一种由希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。要得到自然数 n 以内的全部素数，必须把不大于 $\sqrt{n}$ 的所有素数的倍数剔除，剩下的就是素数。

3. 源码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

int countPrimes(int n)
{
    if (n <= 2) return 0;
    vector<bool> NotPrime(n, false); // bool变量初始为false较好
    int sum = 1;
    int upper = sqrt(n);
    for (int i = 3; i < n; i += 2)
    { // 剔除素数 2 的倍数
        if (!NotPrime[i])
        {
            ++sum;
            if (i > upper) continue;
            for (int j = i*i; j < n; j += i)
            { // 剔除素数 i 的倍数
                NotPrime[j] = true;
            }
        }
    }
    return sum;
}

4. 拓展 — 素数判断

质数 (Prime number)，又称素数，为只有 1 个自身两个因数的数。下面介绍两种判断素数的方法。

  1. 直观判断法

    根据定义判断从 2 到 $\sqrt{n}$ 是否存在 n 的约数即可。

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

    bool isPrime_1(int num)
{
    if (num <= 2)
    {
        if (num == 2) return true;
        return false;
    }
    int upper = sqrt(num);
    for (int i = 2; i <= upper; ++i)
    {
        if (num % i == 0) return false;
    }
    return true;
}

  2. 应用素数分布规律

    素数分布规律：大于等于 5 的素数一定和 6 的倍数相邻。例如 5 和 7，11 和 13，17 和 19 等等。

    证明：令 $x ≥ 1$，将大于等于 5 的自然数表示如下：

    $··· 6x-1，6x，6x+1，6x+2，6x+3，6x+4，6x+5，6(x+1)，6(x+1)+1 ···$

    可以看到，不在 6 的倍数两侧，即不在 $6x$ 两侧的数为 $6x+2$，$6x+3$，$6x+4$，可以表示为 $2(3x+1)$，$3(2x+1)$，$2(3x+2)$，所以它们一定不是素数，显然，素数要出现只可能出现在 $6x$ 的相邻两侧。

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

    bool isPrime_2(int num)
{
    if (num < 5)
    {
        if (num == 2 || num == 3) return true;
        return false;
    }
    /* 不在 6 的倍数两侧的一定不是素数 */
    if ((num % 6 != 1) && (num % 6 != 5)) return false;
    /* 在 6 的倍数两侧的也不一定是素数，需判断 */
    int upper = sqrt(num);
    /* num 为 6x-1 或 6x+1
     * num 为奇数，不能被 6x，6x+2，6x+4 整除
     * num 不可能被 3 整除，故不可能被 6x+3 整除
     * 因此，num 只可能被 6x-1 和 6x+1 形式的数整除 */    
    for (int i = 5; i <= upper; i += 6)
    {
        if ((num % i == 0) || (num % (i+2) == 0)) return false;
    }
    return true;
}

扩展阅读：孪生素数就是指相差 2 的素数对，例如 3 和 5，5 和 7，11 和 13…。孪生素数猜想正式由希尔伯特在 1900 年国际数学家大会的报告上第 8 个问题中提出，可以这样描述：存在无穷多个素数 $p$，使得 $p + 2$ 是素数。素数对 $(p, p + 2)$ 称为孪生素数。