196. 质数距离

L和R的值非常大,我们无法求出[L,R]的所有质数(直接求2^31-1以内的所有质数会超时)
任何一个合数n,它一定有一个不超过√n的质数,所以对于一个质数p,
i∗p就是一个合数,利用上面的性质,我们可以先预处理出[2,√R]的所有质数,然后通过这些
质数去筛出[L,R]中的合数,而在[L,R]中没有被筛到的数,就是质数.

 #include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL; 
const int N = 1e6+10;
int primes[N], cnt;     // primes[x]存储所有2~x的素数
bool st[N];         // st[x]存储x是否被筛掉,true表示x为合数
void getPrimes(int n){
    memset(st, false, sizeof(st));
    for(int i=2; i<=n; i++){
        if(st[i]==false) primes[cnt++]=i;
        for(int j=0; primes[j]<=n/i; j++){
            st[primes[j]*i]=true;
            if(i%primes[j]==0) break;
        }
    }
}

int main(){
    LL l, r;
    while(cin>>l>>r){
        getPrimes(50000);
        memset(st,false,sizeof st);
        for(int i=0; i<cnt; i++){
            int p = primes[i];
            for(LL j=max(((l+p-1)/p*p),2ll*p); j<=r; j+=p){
                st[j-l] = true;//将l~r之间的合数筛除 
            }
        }
        cnt = 0;
        for(int i=0; i<=r-l; i++){
            if(!st[i] && i+l>1){
                primes[cnt++] = i+l; 
            }
        }
        if(cnt < 2) printf("There are no adjacent primes.\n");
        else{
            int minp = 0, maxp = 0;
            for(int i=0; i+1<cnt; i++){
                int tar = primes[i+1] - primes[i];
                if (tar < primes[minp + 1] - primes[minp]) minp = i;
                if (tar > primes[maxp + 1] - primes[maxp]) maxp = i;
            }
            printf("%d,%d are closest, %d,%d are most distant.\n", primes[minp], primes[minp + 1], primes[maxp], primes[maxp + 1]);
        }
    }
    return 0;
}