题目描述

输入一个数，输出 [0...$10^6$] 范围内离它最近的素数。如果该数本身是素数，则输出其本身。

若有两个距离相等，则输出小于它的那个素数。

输入格式

测试数据有 $n$ ( $n \le 10^6$ )组，接下来为 $n$ 行，每行包括一个整数 $m$ ( $0 \lt m \le 10^6$ )。

输出格式

输出有 $n$ 行，每行为离对应 $m$ 最近的一个素数。输出结果的范围与 $m$ 的取值范围相同。

样例

2
22
5

23
5

完善程序

#include<bits/stdc++.h>
using namespace std;
int prime[1000001],tot;
bool f[1000001];
void gen_prime() // 这条题第一个考你的地方是要看出这个地方是做什么的，要背得出来这段代码
{
	int maxn = 1000000;
	for(int i=填空(1);i<=maxn;i++)
	{
		if(填空(2))
		{
			prime[++tot] = i;
			for(int j=2;填空(3)<=maxn;j++)
				f[i*j] = true;
		}
	}
}
int search(int a) //这是本题的第二个考点，这个函数是干嘛的？
{
	int low=1,high=tot,mid;
	
	while(填空(4))
	{
		mid = 填空(5);
		if(prime[mid]>a)
			填空(6);
		else
			填空(7);
	}
	return 填空(8);
}
int main()
{
	int n,t,t1,t2;
	

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

	while(n--)
	{
		scanf("%d",&t);
		
		//要猜测和分析这几个 if 分支分别是属于什么情况。 
		if(t<=prime[1])
			printf("%d\n",prime[1]);
		else if(t>=prime[tot])
			printf("%d\n",prime[tot]);
		else if(填空(9))
			printf("%d\n",t);
		else 
		{
			t2=search(t);
			t1=填空(10); // 这个地方是整条题最需要想象力的地方
			if(t-prime[t1]<=prime[t2]-t)
				printf("%d\n",prime[t1]);
			else
				printf("%d\n",prime[t2]);
		}
	}

	return 0;
}

填空(1)：{{ input(1) }}

填空(2)：{{ input(2) }}

填空(3)：{{ input(3) }}

填空(4)：{{ input(4) }}

填空(5)：{{ input(5) }}

填空(6)：{{ input(6) }}

填空(7)：{{ input(7) }}

填空(8)：{{ input(8) }}

填空(9)：{{ input(9) }}

填空(10)：{{ input(10) }}