題目描述
走進世博園某資訊通信館，參觀者將獲得前所未有的尖端互動體驗，一場充滿創想和喜悅的資訊通信互動體驗秀將以全新形式呈現，從觀眾踏入展館的第一步起，就將與手持終端密不可分，人類未來夢想的驚喜從參觀者的掌上展開，
在等候區的夢想花園中，參觀者便開始了他們奇妙的體驗之旅，等待中的游客可利用手機等終端參與互動小游戲，與夢想劇場內的虛擬人物Kr. Kong 進行猜數比賽，當螢屏出現一個整數X時，若你能比Kr. Kong更快的發出最接近它的素數答案，你將會獲得一個意想不到的禮物，
例如：當螢屏出現22時，你的回答應是23；當螢屏出現8時，你的回答應是7；若X本身是素數，則回答X;若最接近X的素數有兩個時，則回答大于它的素數，
輸入
第一行，一個正整數 n，表示要競猜的整數個數；
接下來的 n 行，每行一個正整數 X，
輸出
輸出有 n 行，每行一個整數，表示與對應 X 的最接近它的素數，
樣例輸入
4
22
5
18
8
樣例輸出
23
5
19
7
提示：對于 100%的資料：n<=1000000,X<=10000000，
素數篩處理出1e7內的所有素數，對篩出的素數進行處理，發現1e7內相鄰2個素數之間的間隔不會超過200，若n是素數則輸出本身，若n不是素數則向上下兩個方向尋找，找到素數就直接輸出，
#include<bits/stdc++.h>
#pragma GCC optimize(2)
#define ll long long
using namespace std;
int _,n,f[10000010];
int main(){
f[1]=1;
for(int i=2;i<=10000000;i++) if(!f[i])
for(int j=2*i;j<=10000000;j+=i) f[j]=1;
scanf("%d",&_);
while(_--){
scanf("%d",&n);
if(!f[n]) printf("%d\n",n);
else if(n&1)
for(int i=2;i<=1000;i+=2){
if(!f[n+i]&&n+i<=10000000){
printf("%d\n",n+i);
break;
}
else if(!f[n-i]&&n-i>=2){
printf("%d\n",n-i);
break;
}
}
else
for(int i=1;i<=1000;i+=2){
if(!f[n+i]&&n+i<=10000000){
printf("%d\n",n+i);
break;
}
else if(!f[n-i]&&n-i>=2){
printf("%d\n",n-i);
break;
}
}
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/250748.html
標籤：其他
上一篇：佇列
下一篇：C#繪制中國象棋棋盤