3910 - 素数的最短距离
输入一个数，输出离它最近的素数.如果该数本身是素数，则输出其本身；
若有两个距离相等，则输出小于它的那个素数。
题目输入
测试数据有N(N<=1000)组，接下来为N行，每行包括一个整数M(0<M<=1000)。
题目输出
输出有N行，每行为离对应M最近的一个素数。输出结果的范围与M的取值范围相同
输入/输出样例
题目输入
2 22 5
题目输出
23 5
C语言解答
#include<stdio.h> int main() { int N,M; scanf("%d",&N); for(int t = 1; t <= N; t++) { scanf("%d",&M); if(M == 1 || M ==2) printf("2\n"); else { int k,num1,num2,s1,s2; for(k = 2; k < M; k++) if( M % k == 0) break; if(k < M) { for(int i = M; i >= 2; i--) { int j; for(j = 2; j < i; j++) if(i % j == 0) break; if(j == i) { s1 = i; num1 = M - i; break; } } for(int i = M;; i++) { int j; for(j = 2; j < i; j++) if(i % j == 0) break; if(j == i) { s2 = i; num2 = i - M; break; } } if(num1 > num2) printf("%d\n",s2); else printf("%d\n",s1); } else printf("%d\n",M); } } return 0; }
C++解答
#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<cmath> #include<algorithm> #include <fstream> #include <limits> #include <vector> #include <list> #include <set> #include <map> #include <queue> #include <stack> #include <cassert> using namespace std; int main() { int t,n; bool a[1010]={1,1,0,0,1}; for(int i=2;i<1005;i++) for(int j=2;j<=i&&i*j<1005;j++) a[i*j]=1; scanf("%d",&t); while(t--) { scanf("%d",&n); for(int i=0;;i++) { if(n-i>0&&a[n-i]==0) { printf("%d\n",n-i); break; } if(n+i<=1000&&a[n+i]==0) { printf("%d\n",n+i); break; } } } return 0; }