首页 > 代码库 > POJ2689 Prime Distance

POJ2689 Prime Distance

题意:输入[l,r]代表,问区间里面最近和最远的两个素数(0<l<r<int_max, r-l<100000)

题解:素数筛,一个数是合数,那么它存在小于sqrt(n)的素因子,找到所有小于sqrt(int_max)的素数,注意数据:1 2

#include <iostream>#include <string.h>#include <stdio.h>#define N 1001000#define ll long longusing namespace std;bool isprime[N], isp[N];long long prime[N], num, ans[N];void doprime(long long n){    long long i,j;    num = 0;    memset(isprime, true,sizeof(isprime));    isprime[1] = 0;    for(i=2;i<=n;i++){        if(isprime[i]){            prime[num++] = i;            for(j=i*i;j<=n;j+=i) isprime[j] = false;        }    }}void doprime2(long long l,long long r){    memset(isp, true, sizeof(isp));    for(long long i=0;i<num;i++){        long long t = l/prime[i];        while(prime[i]*t<l||t<=1) t++;        for(long long j=t*prime[i];j<=r;j+=prime[i])            isp[j-l] = 0;    }    if(l==1) isp[0] = 0;}int main(){    long long ansl,ansr, l, r, ansll, ansrr;    doprime(50000);    while(cin>>l>>r){        doprime2(l,r);        long long t = 0;        for(long long i=l;i<=r;i++)            if(isp[i-l] == 1)                ans[t++] = i;        if(t < 2) printf("There are no adjacent primes.\n");        else{            long long mi = 10000000, ma = -10000000;            for(long long i=0;i<t-1;i++){                if(mi>ans[i+1]-ans[i]){                    ansl = ans[i];                    ansr = ans[i+1];                    mi = ansr-ansl;                }                if(ma < ans[i+1]-ans[i]){                    ansll = ans[i];                    ansrr = ans[i+1];                    ma = ans[i+1]-ans[i];                }            }            printf("%lld,%lld are closest, %lld,%lld are most distant.\n", ansl, ansr, ansll, ansrr);        }    }}

 

POJ2689 Prime Distance