素数距离问题
时间限制：
3000 ms | 内存限制：
65535 KB
难度：
2
- 描述
-
现在给出你一些数，要求你写出一个程序，输出这些整数相邻最近的素数，并输出其相距长度。如果左右有等距离长度素数，则输出左侧的值及相应距离。
如果输入的整数本身就是素数，则输出该素数本身，距离输出0- 输入
-
第一行给出测试数据组数N(0<N<=10000)
接下来的N行每行有一个整数M(0<M<1000000)， - 输出
-
每行输出两个整数 A B.
其中A表示离相应测试数据最近的素数，B表示其间的距离。 - 样例输入
-
3 6 8 10
- 样例输出
-
5 1 7 1 11 1
#include<stdio.h> #include<string.h> #include<math.h> #define N 1500000 bool visit[N]; void prim() { int temp,i,j; temp=(int)sqrt(N+0.5); memset(visit,0,sizeof(visit)); for(i=2;i<=temp;i++) if(!visit[i]) { for(j=i*i;j<=N;j+=i) visit[j]=1; } } /* bool is_prim(int x) { int s; for(s=2;s<=sqrt(1.0*x);s++) if(x%s==0) return false; return true; } */ int main() { prim(); int T,m;int i,j=0,k; int temp1,temp2; scanf("%d",&T); while(T--) { scanf("%d",&m); if(m==1) { printf("2 1\n"); continue; } /* for(i=m;i>1;i--) { if( is_prim(m)) { printf("%d %d\n",m,0); break; } */ for(j=m;j>=1;j--) { if(!visit[j]) temp2=m-j; for(k=m+1;;k++) if(!visit[k]) { temp1=k-m; break; } if(!visit[j]&&!visit[k]) { if(temp1>=temp2) /*等号表示相同情况下应输出左边的*/ printf("%d %d\n",j,temp2); else printf("%d %d\n",k,temp1); break; } } } return 0; }
