博客

/*
    题目描述：给出长度小于1e6的区间[L , R] (1 <= L < R <=2^31)，要求输出区间内距离最远的两个素数和距离最近的
                    的两个素数，如果区间内不足两个素数按照题目要求输出
    
    方法：由定理可知，“n为合数则n一定有不超过√n的素因子”，因此，可以预处理1e5以内的所有素数，在利用这些素数
              对L ， R之间的数进行筛选，用vis数组记录L~R之间的每一个数是否为素数，其中用vis[i]表示i+L是否为素数的
              情况。
*/
#pragma warning(disable:4786)
#pragma comment(linker, "/STACK:102400000,102400000")
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<cmath>
#include<string>
#include<sstream>
#define LL long long
#define FOR(i,f_start,f_end) for(int i=f_start;i<=f_end;++i)
#define mem(a,x) memset(a,x,sizeof(a))
#define lson l,m,x<<1
#define rson m+1,r,x<<1|1
using namespace std;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double PI = acos(-1.0);
const double eps=1e-8;
const int maxn = 1e5 + 5;
int isprime[maxn], vis[10 * maxn];
LL prime[maxn];
int pnum ;
void find_prime(int n)
{
    pnum = 0;
    mem(prime, 0);
    mem(isprime, 1);
    for(int i = 2 ; i < n ; i++){
        if(isprime[i])      prime[pnum++] = i;
        for(int j = 0; j<pnum && i * prime[j] < n ; j++){
            isprime[i * prime[j] ] = 0;
            if(i % prime[j] == 0)       break;
        }
    }
}
int main()
{
    find_prime(1e5 + 2);
    LL L , R;
    while(scanf("%lld %lld",&L,&R)!=EOF){
        mem(vis,1);
        for(LL i = 0 ; i<pnum ; i++){
            if(prime[i] > R)        break;
            LL j = L / prime[i];
            while(j * prime[i] < L)   ++j;
            if(j == 1)      j = 2;
            for( ; j * prime[i] <= R ; j++){
                vis[ j * prime[i] - L ] = 0;
            }
        }
        if( L == 1)     vis[0] = 0;
        LL maxv = - INF , minv = INF , last = -1 ;
        LL maxx , maxy , minx , miny ;
        bool ok = 0;
        for(int i = 0 ; i<= R - L  ; i++){
            if(last == -1 && vis[i])       last = i;
            else if(last != -1 && vis[i]){
                if(maxv < i - last + 1){
                    maxv = i - last + 1;
                    maxx = last ;       maxy = i;
                }
                if(minv > i - last + 1){
                    minv = i - last + 1;
                    minx = last ;       miny = i;
                }
                ok = 1;
                last = i;
            }
        }
        if(ok)
            printf("%lld,%lld are closest, %lld,%lld are most distant.\n",minx + L , miny + L , maxx + L , maxy + L);
        else
            printf("There are no adjacent primes.\n");
    }
    return 0;
}