POJ 2689 Prime Distance：大區間素數篩選與相鄰素數對查找

POJ 2689 Prime Distance：大區間素數篩選與相鄰素數對查找

題目背景

給定區間 [L, U] (1 ≤ L < U ≤ 2,147,483,647)，區間長度 ≤ 1,000,000。找出區間內：

• 距離最近的相鄰素數對 (C1, C2)
• 距離最遠的相鄰素數對 (D1, D2)
• 若素數個數 < 2，輸出 "There are no adjacent primes."

核心算法：區間篩法

因 U 可達 2³¹-1，無法直接篩選。但區間長度 ≤ 10⁶，可用「區間篩法」：

1. 先用普通埃氏篩法求出 √U (≤ 46340) 以內所有素數
2. 建立長度 U-L+1 的布爾陣列標記區間內合數
3. 對每個小素數 p，從 ceil(L/p)*p 開始步長 p 標記合數
4. 剩下的即為區間內素數

關鍵代碼片段

const int INF = 1 << 30;
const int LIM = 60000; // > sqrt(2^31)
int prime[LIM], vis[LIM], cnt;

void init() {
    for (int i = 2; i < LIM; ++i) if (!vis[i]) {
        prime[cnt++] = i;
        for (long long j = 1LL*i*i; j < LIM; j += i) vis[j] = 1;
    }
}

int isPrime[1000005], primes[1000005], pcnt;

int main() {
    init();
    long long L, U;
    while (cin >> L >> U) {
        fill(isPrime, isPrime + (U-L+1), 1);
        if (L == 1) L = 2;

        for (int i = 0; i < cnt && 1LL*prime[i]*prime[i] <= U; ++i) {
            long long start = (L + prime[i] - 1) / prime[i] * prime[i];
            if (start == prime[i]) start += prime[i]; // 避免標記素數本身
            for (long long j = start; j <= U; j += prime[i])
                isPrime[j - L] = 0;
        }

        pcnt = 0;
        for (int i = 0; i <= U-L; ++i)
            if (isPrime[i]) primes[pcnt++] = i + L;

        if (pcnt < 2) {
            cout << "There are no adjacent primes.\n";
            continue;
        }

        int c1=0, c2=0, d1=0, d2=INF;
        for (int i = 1; i < pcnt; ++i) {
            int diff = primes[i] - primes[i-1];
            if (diff > c2 - c1) { c1 = primes[i-1]; c2 = primes[i]; }
            if (diff < d2 - d1) { d1 = primes[i-1]; d2 = primes[i]; }
        }
        cout << d1 << ',' << d2 << " are closest, "
             << c1 << ',' << c2 << " are most distant.\n";
    }
}

複雜度分析

• 預篩：O(√U log log √U) ≈ 5×10⁴ 運算
• 區間篩：∑ (U-L)/p ≈ (U-L) log log U ≤ 10⁶ × 小常數
• 掃描：O(U-L)
• 整體極快，輕鬆通過時限

測試樣例

輸入：
2 17
14 17

輸出：
2,3 are closest, 7,11 are most distant.
There are no adjacent primes.

此題是區間篩法的經典應用，也是處理大範圍素數問題的標準範式。