#include <stdio.h>
#include <cstring>
#include <algorithm>
#include <vector>
#include <iostream>

using namespace std;

typedef unsigned int ll;

int offset_numbers[2000001];
bool sqrt_b[50001];

int n = 0;

#include <cmath>
void prime_block(ll l,ll r)
{
    int maxl = (int)sqrt((double)l);
    int maxv = (int)sqrt((double)r);
    if(maxl == 0)
    {
        maxl = 2;
        sqrt_b[0] = true;
        sqrt_b[1] = true;
    }
    for (ll i = maxl; i <= maxv+1 ; ++i) {
        if(!sqrt_b[i])
        {
            for (ll j = 2*i; j*j <= r; j+=i) {
                sqrt_b[j] = true;
            }


        }
    }
}
void prime_kk(ll l,ll r)
{
    int maxv = (int)sqrt((double)r);
    for (ll i = 2; i <= maxv+1; ++i) {
        if(!sqrt_b[i])
        {
            for (ll k = l%i == 0?l: l + i - l%i ; k < r; k+=i) {
                if(k == i)
                {
                    continue;
                }
                if(k>3)
                {
                    offset_numbers[k-l] = 1;
                }
            }
        }
    }
    if(l == 1)
    {
        offset_numbers[0] = 1;
    }
}
int main() {
    ll l,r;
    memset(sqrt_b,0, sizeof(sqrt_b));//假设全为质数
    prime_block(0,50000);
    while (~scanf("%d %d",&l,&r))
    {
        int mind = 1000001,maxd = 0;
        int minl,minr,maxl,maxr;


        memset(offset_numbers,0, sizeof(offset_numbers));//假设全为质数
        prime_kk(l,r);
        int m = 0;
        int haved = false;
        while (m<=r-l)
        {
            if(!offset_numbers[m] && m <=r-l-1)
            {
                int i = m+1;
                for (;offset_numbers[i] ; ++i) {}
                offset_numbers[m] = i-m-1;

                haved = true;
                if(mind > i-m)
                {
                    mind = i-m;
                    minl = m;
                    minr = i;
                }
                if(maxd < i-m)
                {
                    maxd = i-m;
                    maxl = m;
                    maxr = i;
                }
                m = i;
            } else
            {
                m++;
            }
        }
        if(haved)
        {
            printf("%d,%d are closest, %d,%d are most distant.\n",minl+l,minr+l,maxl+l,maxr+l);
        } else
        {
            printf("There are no adjacent primes.\n");
        }

    }

    return 0;
}

• Re:hhh重新写了一遍过了...确实理清了不少思路 (2473) sailist 2019-03-21 10:53:53
• Re:很多数据都测试过了成功了，句子也确定没有错但还是WA...不知道什么情况 (46) sailist 2019-03-21 10:54:58