UVa 1644 素數間隔：篩法預處理 + 二分查找

題目描述

給定整數 n (n ≤ 1,299,709)，若 n 是素數輸出 0；否則輸出 n 所在的素數間隔長度（即緊鄰 n 的兩個素數之差）。

解題思路

1. 預處理素數表： 埃拉托斯特尼篩法求出 1,300,000 以內所有素數，存入 `vector primes`，並用 `bool isPrime[]` 標記。
2. 查詢處理：
   • 若 `isPrime[n]` 輸出 0。
   • 否則在 `primes` 中二分查找第一個大於 n 的素數 `primes[R]`，則 `primes[R-1] < n < primes[R]`，答案為 `primes[R] - primes[R-1]`。

代碼實現 (C++)

#include 
#include 
#include 
using namespace std;

const int MAXN = 1300000;
bool isComp[MAXN];
vector primes;

void sieve() {
    int limit = sqrt(MAXN) + 1;
    for (int i = 2; i <= limit; i++) {
        if (!isComp[i]) {
            for (int j = i*i; j < MAXN; j += i) isComp[j] = true;
        }
    }
    for (int i = 2; i < MAXN; i++) if (!isComp[i]) primes.push_back(i);
}

int main() {
    sieve();
    int n;
    while (scanf("%d", &n) == 1 && n) {
        if (!isComp[n]) {
            printf("0\n");
        } else {
            // 二分查找第一個 > n 的素數
            int l = 0, r = primes.size() - 1;
            while (l < r) {
                int mid = (l + r) >> 1;
                if (primes[mid] > n) r = mid;
                else l = mid + 1;
            }
            printf("%d\n", primes[l] - primes[l-1]);
        }
    }
    return 0;
}

關鍵點

• 題目給定上界 1,299,709 是第 100,000 個素數，篩法上界設 1,300,000 即可覆蓋。
• 二分查找標準「查找第一個大於目標值的元素」模板。
• 輸入以 0 結束，多測試用例處理。

複雜度

• 預處理：O(N log log N) ≈ 1.3e6 操作，極快。
• 查詢：O(log π(N)) ≈ O(log 1e5) ≈ 17 次比較。
• 空間：O(N) ≈ 1.3MB。