計蒜客第六章：素數距離

計蒜客練習題：素數距離

題目

樣例

思路

先進行質數篩法求全部範圍内質數，在取出區間(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;
}