计蒜客练习题:素数距离
题目
样例
思路
先进行质数筛法求全部范围内质数,在取出区间(l,r)中的质数,最后遍历找出所求。
代码
#include<iostream>
using namespace std;
bool is_prime[8000100];
int a[1000000];
int main()
{
int l,r;
scanf("%d %d",&l,&r);
is_prime[1]=1;//质数筛法
for(int i=2;i*i<=r;++i)
if(!is_prime[i])
for(int j=i*i;j<=r;j+=i)
is_prime[j]=1;
int ma=0,mi=8000000,j=0;
int max1=0,max2=0,min1=0,min2=0;
for(int i=l;i<=r;i++)//存入质数
if(!is_prime[i]) a[j++]=i;
for(int i=1;i<j;i++)//遍历(l,r)区间的质数序列查找
{
if(ma<a[i]-a[i-1])
{
ma=a[i]-a[i-1];
max1=a[i-1];
max2=a[i];
}
if(mi>a[i]-a[i-1])
{
mi=a[i]-a[i-1];
min1=a[i-1];
min2=a[i];
}
}
if(j==0||j==1) printf("There are no adjacent primes.");
else printf("%d,%d are closest, %d,%d are most distant.",min1,min2,max1,max2);
return 0;
}