ACM 24 素数距离问题（记录距离最近的素数）
发布时间
阅读量：
阅读量
写这道题的时候数虽然很大，但遇过类似的题，所以也不是很难，但遇到的问题就是宏定义t的值要是仅仅大于一百万，就不是很够用了，因为距离999999最近的是10000003.所以尽量把范围再大20左右。。。
素数距离问题
时间限制： 3000 ms | 内存限制： 65535 KB
难度： 2
描述 现在给出你一些数，要求你写出一个程序，输出这些整数相邻最近的素数，并输出其相距长度。如果左右有等距离长度素数，则输出左侧的值及相应距离。
如果输入的整数本身就是素数，则输出该素数本身，距离输出0
输入 第一行给出测试数据组数N(0<N<=10000)
接下来的N行每行有一个整数M(0<M<1000000)，
输出 每行输出两个整数 A B.
其中A表示离相应测试数据最近的素数，B表示其间的距离。
样例输入
样例输出
#include<stdio.h>
#define t 1000011//尽可能大20左右
int a[t];
int main()
{
a[0]=a[1]=1;
for(int i=2; i<t; i++)
{
if(!a[i])
{for(int j=i+i; j<t; j+=i)
a[j]=1;
}
}//判断素数
int m,n,s,z,w,k;
scanf("%d",&n);
while(n--)
{
scanf("%d",&m);
if(m==1)
printf("2 1\n");
if(m>1)
{
if(!a[m])
printf("%d 0\n",m);
else
{
for(int i=m+1; i<t; i++)
{
if(!a[i])
{
s=i;
z=i-m;//记录差值
break;
}
}
for(int i=m-1; i>1; i--)
{
if(!a[i])
{
w=i;
k=m-i;//记录差值
break;
}
}
if(z>=k)
printf("%d %d\n",w,k);
else
printf("%d %d\n",s,z);
}
}
}
}全部评论 (0)
还没有任何评论哟~