poj2689：素数筛

题目大意，给定l和u，求区间[l,u]内的素数中，相邻两个差最大和最小的素数
其中 u的范围达到了2e9
本质上需要找出n以内的所有素数，使用筛法。
先保存50000(大于sqrt(2e9))内的所有素数，然后再去筛出区间[l,u]内的素数（题上给定l-u<=1000000）所以可以存下所有素数
又由素数分布定理 素数个数s(n)~n/lnn并不是很大，所以找到所有素数保存在prime[]中扫一遍即可得到答案
代码如下

#include<stdio.h>

#include<string.h>

#include <algorithm>

using namespace std;

#define N 100007

bool isprime0[];

int prime0[];

long long prime[];

bool isprime[];

int num0;

int num;

long long x,y;

void setprime()

{

    num=;

    for(int i=;i<=;i++)

    {

        if(!isprime0[i])

            prime0[num0++]=i;

        for(int j=;j<num0&&prime0[j]*i<=;j++)

        {

            isprime0[i*prime0[j]]=;

            if(!(i%prime0[j]))

                break;

        }

    }

}

void setprime1()

{

    memset(isprime,,sizeof(isprime));

    for(int i=;i<num0;i++)

    {

        long long j=x/prime0[i];

        while(j*prime0[i]<x)

            j++;

        for(j=j*prime0[i];j<=y;j+=prime0[i])

            if(j/prime0[i]>)

                isprime[j-x]=;

    }

    if(x==)

        isprime[]=;

    num=;

    for(long long i=;i<=y-x;i++)

    {

        if(!isprime[i])

            prime[num++]=x+i;

    }

}

int main()

{

    setprime();

    while(scanf("%I64d%I64d",&x,&y)!=EOF)

    {

        setprime1();

        long long a,b,c,d;

        long long mi=,ma=;

        if(num<)

        {

            puts("There are no adjacent primes.");

            continue;

        }

        for(int i=;i+<num;i++)

        {

            long long p=prime[i+]-prime[i];

            if(p<mi)

            {

                a=prime[i];

                b=prime[i+];

                mi=p;

            }

            if(p>ma)

            {

                c=prime[i];

                d=prime[i+];

                ma=p;

            }

        }

        printf("%I64d,%I64d are closest, %I64d,%I64d are most distant.\n",a,b,c,d);

    }

    return ;

}

巴特西

poj2689：素数筛

最新文章

热门文章