8.3 質數

質數又稱素數，指的是在大於 1 的自然數中，除了 1 和它本身以外不再有其他因數的自然數。值得注意的是，每一個數都可以分解成質數的乘積。

204. Count Primes

題目描述

給定一個數字 n，求小於 n 的質數的個數。

輸入輸出範例

輸入一個整數，輸出也是一個整數，表示小於輸入數的質數的個數。

Input: 10
Output: 4

在這個範例中，小於 10 的質數只有 [2, 3, 5, 7]。

題解

埃拉托斯特尼篩法（Sieve of Eratosthenes，簡稱埃氏篩法）是非常常用的，用於判斷一個整數是否為質數的方法。它也可以在判斷一個整數 $n$ 時，同時判斷所有小於 $n$ 的整數，因此非常適合這道題目。其原理也十分簡單：從 $1$ 到 $n$ 遍歷，假設當前遍歷到 $m$，則把所有小於 $n$ 且是 $m$ 的倍數的整數標記為和數；遍歷完成後，沒有被標記為和數的數字即為質數。

C++

int countPrimes(int n) {
    if (n <= 2) {
        return 0;
    }
    vector<bool> primes(n, true);
    int count = n - 2;  // 移除不是質數的 1
    for (int i = 2; i < n; ++i) {
        if (primes[i]) {
            for (int j = 2 * i; j < n; j += i) {
                if (primes[j]) {
                    primes[j] = false;
                    --count;
                }
            }
        }
    }
    return count;
}

Python

def countPrimes(n: int) -> int:
    if n <= 2:
        return 0
    primes = [True for _ in range(n)]
    count = n - 2 # 移除不是質數的 1
    for i in range(2, n):
        if primes[i]:
            for j in range(2 * i, n, i):
                if primes[j]:
                    primes[j] = False
                    count -= 1
    return count

利用質數的一些性質，我們可以進一步優化該演算法。

C++

int countPrimes(int n) {
    if (n <= 2) {
        return 0;
    }
    vector<bool> primes(n, true);
    int sqrtn = sqrt(n);
    int count = n / 2;  // 偶數一定不是質數
    int i = 3;
    // 最小質因子一定小於等於平方根。
    while (i <= sqrtn) {
        // 向右找倍數，注意避免偶數和重複遍歷。
        for (int j = i * i; j < n; j += 2 * i) {
            if (primes[j]) {
                --count;
                primes[j] = false;
            }
        }
        i += 2;
        // 向右前進查找位置，注意避免偶數和重複遍歷。
        while (i <= sqrtn && !primes[i]) {
            i += 2;
        }
    }
    return count;
}

Python

def countPrimes(n: int) -> int:
    if n <= 2:
        return 0
    primes = [True for _ in range(n)]
    sqrtn = sqrt(n)
    count = n // 2  # 偶數一定不是質數
    i = 3
    # 最小質因子一定小於等於平方根。
    while i <= sqrtn:
        # 向右找倍數，注意避免偶數和重複遍歷。
        for j in range(i * i, n, 2 * i):
            if primes[j]:
                count -= 1
                primes[j] = False
        i += 2
        # 向右前進查找位置，注意避免偶數和重複遍歷。
        while i <= sqrtn and not primes[i]:
            i += 2
    return count