JD 1040 Prime Number：埃拉托斯特尼篩法求第 K 個質數

題目要求

輸出第 k 個質數。多組輸入，k 範圍隱含需預計算足夠多質數。

篩法原理

1. 列出 2~N 所有整數。
2. 最小未篩除數為質數（如 2），劃去其所有倍數。
3. 下一個未篩除數（3）為質數，劃去倍數。
4. 重複至 √N，剩餘未篩除數皆為質數。

代碼實現

#include 
#include 
#include 
#include 
using namespace std;
const int N = 1000000;
bool prime[N];

void init_prime() {
    memset(prime, 1, sizeof(prime));
    prime[0] = prime[1] = 0;
    double limit = sqrt(N) + 1;
    for (int i = 2; i < limit; i++) {
        if (prime[i]) {
            for (int j = i + i; j < N; j += i)
                prime[j] = false;
        }
    }
}

int main() {
    init_prime();
    int k;
    while (cin >> k) {
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            if (prime[i]) {
                if (++cnt == k) { cout << i << endl; break; }
            }
        }
    }
    return 0;
}

關鍵點

• `N=1e6` 足夠覆蓋前 78,498 個質數，滿足典型 k 範圍。
• 外層迴圈至 `sqrt(N)` 即可，內層從 `i+i` 步長 `i` 標記合數。
• 查詢時線性掃描 `prime[]` 計數，單次 O(N)，多查詢可預存質數列表 O(1) 回答。

優化方向

• 只篩奇數（節省一半空間與時間）。
• 位壓縮 `bitset` 或 `vector`。
• 線性篩（歐拉篩）O(N) 獲取所有質數並可求最小質因數。