線性篩素數詳解

一、簡介

線性篩素數，顧名思義，是一種用線性時間複雜度求出所有素數的方法。相比於其他素數篩法，線性篩素數更加高效，因此在實際應用中經常被使用。

二、原理

線性篩素數的核心思想是將每個數都標記為「素數」或「合數」，並在記錄同時篩選掉它的所有倍數，這使其無需對每個數都判斷是否是素數。

三、實現

首先，需要創建一個長度為n+1的數組isPrime，用來標記每個數是否為素數

bool isPrime[MAX_N + 1];  // MAX_N為所求最大值

一開始，將isPrime數組置為true，表示假設所有數都為素數。

for (int i = 2; i <= MAX_N; i++) {
    if (isPrime[i]) {  // 若i為素數
        prime[++cnt] = i;  // 將其加入素數數組中
    }

    for (int j = 1; j <= cnt && i * prime[j] <= MAX_N; j++) {
        isPrime[i * prime[j]] = false;  // 篩去合數
        if (i % prime[j] == 0) {  // 優化2
            break;
        }
    }
}

其中，主循環枚舉i從2到n，若i為素數，則將它加入素數數組中，並遍歷它的所有倍數j，將它們標記為合數。在遍歷的過程中，若發現當前數i是某個素數的倍數，那麼就停止遍歷i的倍數，因為它已經被篩選掉了。

四、優化

在實際應用中，線性篩素數還有一些優化操作，可以進一步提高效率。

1、使用已有的素數數組

仔細觀察上述代碼可以發現，每次篩選合數時都要遍歷已經求得的素數數組。這乍一看，效率還不如普通的試除法，但是其時間複雜度是線性的，實際效率也很高。但是，我們可以想到一個優化，那就是直接使用已經求得的素數來篩選。

for (int j = 1; j <= cnt && i * prime[j] <= MAX_N; j++) {
    isPrime[i * prime[j]] = false;
    if (i % prime[j] == 0) {
        break;
    }
}

通過使用已有的素數數組，在篩選的過程中，不僅效率提高了，同時也減少了計算量。

2、拆分判斷

接着，我們可以注意到，在上述代碼中，除數同為質數時，同樣的操作被執行了多次。比如，當i是2的倍數時，就需要將2從它的所有倍數中篩掉；當i是3的倍數時，需要將3從它的所有倍數中篩掉。在這種情況下，代碼中會重複調用，算法效率會受到影響。那麼是否可以做一些調整，提高執行效率呢？答案是肯定的，在這裡我們可以把這些操作拆分開來，以減少重複操作。

for (int j = 1; j <= cnt && i * prime[j] <= MAX_N; j++) {
    isPrime[i * prime[j]] = false;
    if (i % prime[j] == 0) {
        break;
    }
}

3、減少判斷次數

最後，我們需要注意到，當我們在判斷某個數是否為素數時，實際上只需要判斷它是否是當前素數數組中所有素數的倍數就可以了。顯然，這個數可不是所有數的倍數，因此，以它為起點遞增的倍數也不可能是所有數的倍數，只有遞增素數的倍數能夠被篩掉。基於此，我們可以減少判斷次數。

for (int j = 1; j <= cnt && i * prime[j] <= MAX_N; j++) {
    isPrime[i * prime[j]] = false;
    if (i % prime[j] == 0) {
        break;
    }
}

五、總結

線性篩素數是一種高效的素數判定方法，通過將每個數都標記為「素數」或「合數」，並在記錄同時篩選掉它的所有倍數，實現了無需對每個數都判斷是否是素數。在實際應用中，可以通過使用已有的素數數組、拆分判斷和減少判斷次數等方式，進一步提高算法效率。

六、完整代碼

const int MAX_N = 1000000;

bool isPrime[MAX_N + 1];
int prime[MAX_N + 1];
int cnt = 0;

void linearSieve() {
    for (int i = 2; i <= MAX_N; i++) {
        if (isPrime[i]) {
            prime[++cnt] = i;
        }

        for (int j = 1; j <= cnt && i * prime[j] <= MAX_N; j++) {
            isPrime[i * prime[j]] = false;
            if (i % prime[j] == 0) {
                break;
            }
        }
    }
}

int main() {
    memset(isPrime, true, sizeof(isPrime));
    linearSieve();

    for (int i = 1; i <= cnt; i++) {
        printf("%d\n", prime[i]);
    }

    return 0;
}