C++ 素數對計數：相鄰整數且和為素數的枚舉優化與篩法預計算

問題重述

給定區間 [l, r] (0 ≤ l, r ≤ 500)，計算滿足條件的整數對 (a, b) 數量：
1. b = a + 1 (相鄰)
2. a + b 為素數
3. l ≤ a, b ≤ r

數學轉換

a + b = a + (a+1) = 2a + 1。
條件等價於：**2a + 1 為素數**，且 a ∈ [l, r-1]。

暴力枚舉 (數據範圍極小，完全可行)

bool isPrime(int x) {
    if (x < 2) return false;
    for (int i = 2; i * i <= x; i++)
        if (x % i == 0) return false;
    return true;
}

int countPairs(int l, int r) {
    int ans = 0;
    for (int a = l; a <= r - 1; a++)
        if (isPrime(2 * a + 1)) ans++;
    return ans;
}

複雜度：O((r-l) * sqrt(r))，r ≤ 500 時 < 1ms。

優化：埃氏篩預計算素數表 (適用多測試用例)

const int MAXR = 500;
bool isPrime[MAXR * 2 + 2];

void sieve() {
    fill(begin(isPrime), end(isPrime), true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i * i < MAXR * 2 + 2; i++)
        if (isPrime[i])
            for (int j = i * i; j < MAXR * 2 + 2; j += i)
                isPrime[j] = false;
}

int countPairsFast(int l, int r) {
    int ans = 0;
    for (int a = l; a <= r - 1; a++)
        if (isPrime[2 * a + 1]) ans++;
    return ans;
}

樣例驗證

輸入 0 13 → a ∈ [0,12]，2a+1 ∈ {1,3,5,...,25} 中素數為 {3,5,7,11,13,17,19,23} → 8 個，符合樣例輸出。

邊界情況

• l == r：區間無相鄰整數，答案 0。
• l > r：題目保證 l ≤ r，若無保證需交換或返回 0。
• 2a+1 最大為 2*499+1=999，篩法上限 1000 即可。