nyoj-24-素数距离问题

素数距离问题

时间限制： 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

思路：写一个判断素数的函数，然后分别向两边搜索，要注意的是  m=1时的情况。

#include<iostream> #include<cstdio> #include<cmath> using namespace std; int is_prime(int x) { double n=sqrt(x); int t=1; if(x==0||x==1) t=0; else { for(int i=2;i<=n;i++) { if(x%i==0) { t=0;break; } } } } int main() { int T; cin>>T; while(T--) { int a,b=0,c=0; cin>>a; if(a==1) { printf("2 1\n"); } else { int i,j; for(i=a;!is_prime(i);i--) b++; for(j=a;!is_prime(j);j++) c++; if(b<=c) { printf("%d %d\n",i,b); } else { printf("%d %d\n",j,c); } } } return 0; }