求素數的個數

本文將從演算法原理、性能優化、應用場景三方面對求素數的個數進行詳細的闡述。

一、演算法原理

求素數的個數，是計算小於非負整數 n 的質數個數。

這裡介紹兩種演算法：

1、暴力枚舉演算法

暴力枚舉演算法即對於區間 [2, n) 中的每一個數字都進行素數判斷，判斷該數能否被 2~sqrt(n) 之間的數字整除。例如：

bool is_prime(int n) {
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) return false;
    }
    return n != 1;
}

int countPrimes(int n) {
    int count = 0;
    for (int i = 2; i < n; i++) {
        if (is_prime(i)) count++;
    }
    return count;
}

暴力枚舉演算法時間複雜度為 O(n * sqrt(n))，效率較低，不適用於大規模數據計算。

2、篩法演算法

篩法演算法的基本思想是在區間 [2, n) 中，先將 2 的倍數全部標記為合數，然後再取最小的未被標記的數字（即質數），再將這個質數的倍數全部標記為合數。以此類推，直到區間 [2, n) 中的所有數字都被標記，剩下的未被標記的數即為質數。

int countPrimes(int n) {
    bool is_prime[n];
    int count = 0;
    memset(is_prime, true, sizeof(is_prime));
    for (int i = 2; i < n; i++) {
        if (is_prime[i]) {
            count++;
            for (int j = 2; i * j < n; j++) {
                is_prime[i * j] = false;
            }
        }
    }
    return count;
}

篩法演算法時間複雜度為 O(n * log(log(n)))，比暴力枚舉演算法效率更高，適用於大規模數據計算。

二、性能優化

雖然篩法演算法已經比暴力枚舉演算法效率更高，但是在大規模數據計算時，還可以進行更多的性能優化。主要包括以下方面：

1、埃氏篩法演算法

埃氏篩法演算法與篩法演算法類似，但是在標記合數時只需要從 i*i 開始標記即可，因為比 i*i 小的數已經被之前的質數標記過了。例如：

int countPrimes(int n) {
    bool is_prime[n];
    int count = 0;
    memset(is_prime, true, sizeof(is_prime));
    for (int i = 2; i * i < n; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j < n; j += i) {
                is_prime[j] = false;
            }
        }
    }
    for (int i = 2; i < n; i++) {
        if (is_prime[i]) count++;
    }
    return count;
}

埃氏篩法演算法比篩法演算法略快，但是空間佔用較大。

2、線性篩法演算法

線性篩法演算法是對埃氏篩法演算法進行的優化。基本思想是將素數存入數組 prime 中，然後再對區間 [2, n) 中的數字進行分解質因數。例如：

int countPrimes(int n) {
    bool is_prime[n];
    int count = 0;
    memset(is_prime, true, sizeof(is_prime));
    vector prime;  // 用於存放素數
    for (int i = 2; i < n; i++) {
        if (is_prime[i]) {
            prime.push_back(i);  // 將素數存入數組 prime 中
        }
        for (int j = 0; j < prime.size() && i * prime[j] < n; j++) {
            is_prime[i * prime[j]] = false;
            if (i % prime[j] == 0) break;
        }
    }
    for (int i = 2; i < n; i++) {
        if (is_prime[i]) count++;
    }
    return count;
}

線性篩法演算法優勢在於時間和空間上的佔用都比較小。

三、應用場景

求素數的個數雖然看起來簡單，但是在實際應用中也有很多場景可供選擇，例如：

1、數據加密

在密碼學中，求素數的個數是RSA公鑰加密演算法的重要組成部分。RSA公鑰加密演算法就是通過使用兩個大質數作為公鑰，加密信息，只有通過解密才能得到原文。如果質數被不當地選擇，可能會導致信息不安全。因此，選擇合適的素數對於加密過程來說至關重要。

2、質數篩選

質數篩選是指在一個區間內，找到所有質數的過程。這在很多場景中都有應用，例如找到一個範圍內所有質數，來計算兩個數字之間質數的個數；或者是為了避免在計算中重複使用素數，需要預處理一個素數集合。

3、統計學問題

在統計學中，求素數的個數也有應用場景。例如：歐拉定理需要計算 φ(p)，其中 p 是素數，計算公式是：φ(p)=(p-1)。如果能夠快速計算素數的個數，那麼就可以快速地計算 φ(p)。

4、計算大質數

計算大質數是密碼學應用之一。求素數的個數可以用於計算較大的質數。對於有些情況下，需要選擇大於某些最小長度的合適數的質數，此時就需要使用一種能夠高效計算質數的演算法。