洛谷P2640题终极攻略：素数间距问题的高效解法与优化技巧 | 新手必读

1天前洛谷题解56

一、问题理解与算法思路

题目要求找出给定区间[2,n]内所有相差为k的素数对。这道题考察了两个核心算法点：素数判断和高效搜索。我们采用预生成素数表+双指针检查的方法，既保证了正确性又提高了效率。

解题关键步骤：

预先生成2到n的所有素数
使用双指针检查所有可能的素数对间距
及时终止不必要的检查以提高效率

二、完整代码实现（带详细注释）

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
// 优化后的素数判断函数，时间复杂度O(√n) 
bool isPrime(int num) { 
    if (num <= 1) return false; // 1及以下不是素数 
    if (num <= 3) return true; // 2和3是素数 
    if (num % 2 == 0 || num % 3 == 0) return false; // 排除2和3的倍数
    // 检查6k±1形式的因数
    for (int i = 5; i * i <= num; i += 6) {
        if (num % i == 0 || num % (i + 2) == 0) return false;
    }
    return true;
}
int main() { 
    int n, k; 
    cin >> n >> k;
    vector<int> primes;
    // 预先生成2到n的所有素数
    for (int i = 2; i <= n; ++i) {
        if (isPrime(i)) primes.push_back(i);
    }

    bool found = false;
    // 检查所有可能的素数对间距
    for (int i = 0; i < (int)primes.size(); ++i) {
        for (int j = i + 1; j < (int)primes.size(); ++j) {
            int diff = primes[j] - primes[i];
            if (diff == k) {
                cout << primes[i] << " " << primes[j] << "\n";
                found = true;
            } else if (diff > k) {
                break; // 提前终止内层循环
            }
        }
    }

    if (!found) {
        cout << "empty\n";
    }

    return 0;
}