题目24: 素数距离问题
如果输入的整数本身就是素数，则输出该素数本身，距离输出0
- 输入
- 第一行给出测试数据组数N(0<N<=10000)
接下来的N行每行有一个整数M(0<M<1000000)， - 输出
- 每行输出两个整数 A B.
其中A表示离相应测试数据最近的素数，B表示其间的距离。 - 样例输入
36810
- 样例输出
5 17 111 1
- 来源
- 经典题目
/********************************** 日期：2013-3-26* 作者：SJF0115* 题号: 题目24: 素数距离问题* 来源：http://acm.nyist.net/JudgeOnline/problem.php?pid=24* 结果：AC* 来源：南阳理工OJ* 总结：**********************************/#include<stdio.h>#include<string.h>#include<math.h>#define MAX 1000010int prime[MAX];//素数表void Prime(){memset(prime,0,sizeof(prime));for(int i = 2;i < sqrt(MAX)+1;i++){if(prime[i]){continue;}else{for(int j = i*i;j < MAX;j += i){prime[j] = 1;}}}}int main(){int N,M,LIndex,RIndex;//freopen("C:\\Users\\SJF\\Desktop\\acm.txt","r",stdin);Prime();prime[1] = 1;prime[0] = 1;scanf("%d",&N);//N组测试数据while(N--){scanf("%d",&M);if(prime[M] == 0){printf("%d 0\n",M);}else{RIndex = M;LIndex = M;//寻找左边素数while(prime[LIndex] == 1 && LIndex >= 0){LIndex --;}//寻找右边素数while(prime[RIndex] == 1){RIndex ++;}//左边没有找到if(LIndex < 0){printf("%d %d\n",RIndex,RIndex-M);}//左右都有else if(M - LIndex <= RIndex - M){printf("%d %d\n",LIndex,M-LIndex);}else{printf("%d %d\n",RIndex,RIndex-M);}}}return 0;}注意：求素数表时MAX取值要大于1000003.因为距离999999最近的素数就是1000003