POJ 1595 素數打表輸出中間區間：篩法預處理+邊界處理

POJ 1595 素數打表輸出中間區間：篩法預處理+邊界處理

給定 N, C，輸出 N 以內（含 N）素數的中間 2*C-1（素數個數為奇）或 2*C（偶）個素數。N ≤ 1000，多測試用例。

解題步驟

1. 埃氏篩預處理：isprime[] 標記，prime[] 存儲素數列表，nprime 計數。
2. 判斷輸出範圍：
   • 若 nprime < 2*C：輸出所有素數。
   • 奇數個素數：中間 2*C-1 個，索引 [(nprime-(2*C-1))/2, (nprime+(2*C-1))/2)。
   • 偶數個素數：中間 2*C 個，索引 [(nprime-2*C)/2, (nprime+2*C)/2)。
3. 格式控制：N C: p1 p2 ... 雙換行分隔用例。

關鍵代碼

void doprime(int n) {
    nprime = 1; prime[0] = 1;
    memset(isprime, true, sizeof(isprime));
    isprime[1] = false;
    for (int i = 2; i <= n; i++) if (isprime[i]) {
        prime[nprime++] = i;
        for (int j = i*i; j <= n; j += i) isprime[j] = false;
    }
}
int main() {
    while (cin >> n >> c) {
        doprime(n);
        // 邊界判斷與輸出...
    }
}

易錯點

• 素數表包含 1（題目約定），prime[0]=1, nprime=1 起始。
• 索引計算務必用整數除法，注意括號優先級。
• 輸出格式：冒號後一空格，素數間一空格，每用例後空行。

複雜度

• 篩法：O(N log log N) ≈ 1e4 操作。
• 查詢：O(1)。

本題考察基礎篩法與邊界條件處理，代碼短小但細節決定成敗。