解题思路

屏幕每次出现一个整数 X，要快速说出离 X 最近的素数：

• 如果 X 本身就是素数，答案就是 X；
• 如果有两个素数一样近（X 正好在它们正中间），就回答大于 X 的那个。

比如样例：X=22 时，离它最近的素数是 23；X=8 时是 7；X=18 时，17 和 19 一样近，回答 19。

难点：X 最大是 10000000（一千万），询问次数最多 1000000（一百万）。如果每个 X 都从头一个个试，会非常慢。所以我们要先把所有素数“一次性”筛出来，存好，以后每次直接查。

第一步：埃氏筛法求素数

先假设 2 到 MAX 全是素数；然后从 2 开始，把每个素数的倍数都划掉（标成不是素数）。筛完剩下没被划掉的就是素数。这里 MAX 取 10010000，比最大的一千万稍微大一点，这样 X 上方最近的素数也能被筛到。

第二步：二分查找最近的素数

把所有素数存进数组 primes。对每个 X：

• 如果 X 是素数，直接输出 X；
• 否则，用二分查找在 primes 里找第一个大于 X 的素数 hi，它前一个就是小于 X 的最近素数 lo；
• 比较两个距离：如果 hi - X 更小，输出 hi；如果 X - lo 更小，输出 lo；如果一样大，输出 hi（题目要求一样近时选大的）；
• X = 1 要特判，离 1 最近的素数是 2。

二分查找每次只需要比较大约 20 次，一百万次询问也很快。

参考代码

// P4438 最接近的素数：对每个 X，找出离它最近的素数；若一样近则输出较大的那个
#include <iostream>
using namespace std;

const int LIMIT = 10010000;       // 筛的范围，比最大 X=1e7 稍大，保证能覆盖 X 上方最近的素数
bool isP[10010005];               // 标记是否为素数
int primes[700000];               // 保存筛出的素数，1e7 以内素数约 66 万个
int cnt = 0;                      // 素数个数

int main() {
    ios::sync_with_stdio(false);  // 加快输入输出
    cin.tie(0);

    // 素数筛（埃氏筛）：先假设 2~LIMIT 全是素数
    for (int i = 2; i <= LIMIT; i++) isP[i] = true;
    for (int i = 2; 1LL * i * i <= LIMIT; i++) {
        if (isP[i]) {                     // i 是素数，就把它的倍数都划掉
            for (int j = i * i; j <= LIMIT; j += i)
                isP[j] = false;
        }
    }
    for (int i = 2; i <= LIMIT; i++)      // 把素数收集进数组
        if (isP[i]) primes[cnt++] = i;

    int n;
    cin >> n; // 要竞猜的整数个数
    while (n--) {
        int x;
        cin >> x; // 屏幕上出现的整数

        if (x < 2) { cout << 2 << char(10); continue; } // 1 最近的素数是 2，char(10)是换行
        if (isP[x]) { cout << x << char(10); continue; } // X 本身就是素数

        // 二分查找：找到第一个大于 x 的素数（primes 里没有等于 x 的素数）
        int l = 0, r = cnt - 1;
        while (l < r) {
            int mid = (l + r) / 2;
            if (primes[mid] <= x) l = mid + 1;
            else r = mid;
        }
        // l 现在指向"第一个大于 x 的素数"
        int hi = primes[l];          // 比 x 大的最近素数
        int lo = primes[l - 1];      // 比 x 小的最近素数
        if (hi - x <= x - lo) cout << hi << char(10); // 上方更近或一样近（一样近选大的）输出上方
        else cout << lo << char(10);                    // 下方更近输出下方
    }
    return 0;
}

复杂度分析

• 筛素数的复杂度约是 O(MAX × log log MAX)，MAX = 10010000，只要运行一次；
• 每次询问用二分查找，复杂度是 O(log P)，P 是素数个数（约 66 万），即使有一百万次询问也很快；
• 空间上需要一个长度约 1000 万的 bool 数组和保存素数的数组，约 O(MAX)。