算法题：素数

问题描述

当屏幕出现一个整数X时，若你能很快地发现最接近它的素数答案，你将会获得一个意想不到的礼物。

例如，当屏幕出现22时，你的回答是23，当屏幕出现8时，你的回答应该是7。若X 本身是素数，则回答X；若接近X的素数有两个时，则回答最接近它的素数。

输入格式

输入文件的第一行，一个正整数n，表示要竞猜的整数个数；接下来的n行，每行一个正整数X。

输出格式

输出文件有n行，每行一个整数，表示与对应X的最接近它的素数。

样例

输入

4
22
5
18
8

输出

23
5
19
7

数据范围

• 30%的数据：n≤10000，X≤10000
• 60%的数据：n≤100000，X≤1000000
• 100%的数据：n≤1000000, x≤10000000

解决方案

思路

筛选法求素数

代码

#include <iostream>

using namespace std;

int arr[10000000];

int main() {

    int n;
    scanf("%d", &n);

    for (int i = 2; i < 10000000; ++i) {

        if (arr[i] == 0)
            for (int  j = i + i; j < 10000000; j += i) {
                arr[j] = 1;
            }
    }

    for (int  i = 0; i < n; ++i) {
        int t;
        scanf("%d", &t);
        for (int  j = 0; t + j < 10000000 || t - j >= 0; ++j) {
            if (t + j < 10000000 && arr[t + j] == 0) {
                printf("%d\n", t + j);
                break;
            } else if (t - j >= 0 && arr[t - j] == 0) {
                printf("%d\n", t - j);
                break;
            }
        }
    }

    return 0;
}