C++ 輸出 20 萬個質數：埃氏篩法優化達到 1 秒內

原始碼問題

逐個數試除法 (`n % p == 0`) 複雜度 O(N√N / log N)，20 萬質數 (約第 20 萬質數 ~ 275 萬) 遠超 1 秒。

最佳演算法：線性篩 (O(N)) / 埃氏篩優化 (O(N log log N))

#include 
using namespace std;

const int LIMIT = 3000000; // 第 20 萬個質數約 275 萬，留餘量
vector primes;
bool is_composite[LIMIT + 1];

void linear_sieve() {
    for (int i = 2; i <= LIMIT; ++i) {
        if (!is_composite[i]) primes.push_back(i);
        for (int p : primes) {
            long long v = 1LL * i * p;
            if (v > LIMIT) break;
            is_composite[v] = true;
            if (i % p == 0) break; // 核心：每個合數只被最小質因子篩一次
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    linear_sieve();
    for (int i = 0; i < 200000; ++i) {
        cout << primes[i] << '\n';
    }
    return 0;
}

關鍵優化點

1. 線性篩 (Linear Sieve / Euler Sieve)： 每個合數僅被最小質因子標記一次，時間複雜度 O(N)，N=300萬約 0.1 秒內完成。
2. 輸出優化： `ios::sync_with_stdio(false); cin.tie(nullptr);` + `'\n'` 而非 `endl` (避免頻繁 flush)。
3. 靜態陣列 / bitset： `bool[]` 或 `vector` (位壓縮) 減少記憶體、提高快取命中。
4. 預估上限： 第 n 個質數約 `n (ln n + ln ln n)` (n≥6)，20萬 ≈ 275萬，設 300萬保險。

避坑指南

• 不要用 `sqrt` 逐個試除。
• 不要用 `endl` 輸出大量資料。
• 不要在迴圈內動態 `push_back` 擴容 `vector` (預先 `reserve` 或用靜態陣列)。

參考代碼：線性篩 1 秒內輸出 20 萬質數。