💡题目回顾

给定一个正整数 $k$，若 $k$ 是合数，且在两个素数之间（即不为素数），那么我们定义其所在的两个素数 $p$ 和 $q$ 之间存在一个素数间隙，其长度为 $q - p$。程序需要输出该素数间隙的长度。如果 $k$ 本身是素数，输出 0。

✅思路分析

🔹1. 素数筛选（埃拉托色尼筛法）

• 使用一个布尔数组 isprime[] 来标记所有的素数。
• 范围是 $[2, \text{MAXN}]$，其中 $\text{MAXN} = 10^7+5$。
• 我们最多需要找到第 $100000$ 个素数，因此设置一个计数器 num，当 num == 100000 时停止筛选。

🔹2. 查询处理

对于每个输入的正整数 $n$：

• 若 n 是素数，则直接输出 0。
• 若 n 是合数，向左右扩展查找距离最近的素数，求它们之间的距离（间隙长度）。

✅边界处理

• 保证输入 $1 < k \leq 1299709$。
• 当输入为 0 时，终止处理。

✅完整代码（C++）

#include<iostream>
#include<cstring>
#include<cmath>
#include <cstdio>
#define ll long long
#define MAXN 10000005
#define maxn 100005
using namespace std;

bool isprime[MAXN];
ll num = 0;

void checkprime() {
    memset(isprime, true, sizeof(isprime));
    num++;//因为2也是素数
    for(ll i = 2; num <= maxn; i++) {
        if(isprime[i]) {
            num++;//如果没有标记的话就是素数，标记个数
            for(ll j=i+i; j <= MAXN; j+=i) {//以i为倍数的数都是偶数，都不是素数，全部筛除
                isprime[j] = false;
            }
        }
    }
}

int main () {
    int n;
    checkprime();
    while(cin >> n && n) {
        int ans = 1;
        if(isprime[n]) puts("0");
        else {
            int l = n-1, r = n;//预处理向左
            while(!isprime[l]) {//向左
                l--;
                ++ans;
            }
            while(!isprime[r]) {//向右
                r++;
                ++ans;
            }
            printf("%d\n", ans);
        }
    }
    return 0;
} 

📌样例解释

输入：

10
11
27
2
492170
0

输出：

4
0
6
0
114

• 10 是合数，最近素数为 7 和 11，间隙长度 $= 11 - 7 = 4$
• 11 是素数，输出 0
• 27 是合数，最近素数为 23 和 29，间隙长度 $= 6$
• 2 是素数，输出 0
• 492170 是合数，最近素数为 492113 和 492227，间隙长度 $= 114$

⏱复杂度分析

• 预处理筛法时间复杂度： $O(N \log \log N)$
• 每次查询最坏情况左右各扫 $O(G)$ 步，$G$ 是最大间隙长度，实际较快。