有T组测试数据,每组数据给一个整数x。
计算是否存在这样的一个连续整数区间使得这个区间里的数加起来为素数。如果存在,输出这个整数区间的最短长度,否则输出-1.
1<=T<=106
−107<=x<=107
样例输入:
10
-2
-1
0
1
2
3
4
5
6
7
样例输出:
6
4
3
2
1
1
2
1
2
1
我的代码如下,就是找数学规律,如果是负数,就判断一下,改为正数再计算,但是答案错误了。
#include<cstdio>
int T;
bool prime[20000005];
const int M=20000005;
int x;
inline void init(){
prime[0]=prime[1]=1;
for(int i=4;i<=M;i+=2)
prime[i]=1;
for(int i=3;i<=M;i+=2){
if(prime[i]) continue;
for(int j=i+i;j<=M;j+=i)
prime[j]=1;
}
}
inline int cal(int n){
bool f=0;
int ans=0;
if(n<0)
ans=-2*n+1,n=-n+1,f=1;
//printf("%d %d %d\n",n,ans,n);
if(!prime[n]) return ans+1;
if(!prime[n+n-1]||!prime[n+n+1]) return ans+2;
for(int i=1;;++i){
if(!prime[n+i])
return f?ans+i+2:2*n+i;
if(!prime[n+n+i+i+1])
return f?ans+i+3:2*n+i+1;
}
return -1;
}
int main(){
scanf("%d",&T);
init();
while(T--){
scanf("%d",&x);
int ans=0;
if(x==0)
ans=3;
else
ans=cal(x);
printf("%d\n",ans);
}
return 0;
}