首页 > 代码库 > poj 3518 Prime Gap 二分查找下界和素数筛法
poj 3518 Prime Gap 二分查找下界和素数筛法
/*
题意:输入有多组数据,每组数据一个n,如果n是素数,输出0否则输出离n最近的两个素数的积,第100000个素数是1299709,所有的素数都在这个范围内
思路:素数筛法加二分查找下界
*/
#include<stdio.h>
int a[1299720],pri[100005];int Serch(int v)//二分查找下界
{
int mid,x=0,y=100001;
while(x<y)
{
mid=(y+x)/2;
if(pri[mid]>=v)
y=mid;
else
x=mid+1;
}
//printf("pri[x]=%d\n",x);
if(pri[x]==v)
return 0;
else
return pri[x]-pri[x-1];
}
int main()
{
int i,j,k=0,n;
for(i=2; i<=1299709; i++)//筛法
if(!a[i])
{
pri[k++]=i;
for(j=i*2; j<=1299709; j+=i)
a[j]=1;
}
while(~scanf("%d",&n),n)
{
printf("%d\n",Serch(n));
}
return 0;
}
poj 3518 Prime Gap 二分查找下界和素数筛法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。