二次筛法

(写法与y总一致，素数只初始化一次)

1. 筛选区间上限为N 则首先需要筛选2~log2N的素数，再通过区间左端点作为偏移量，映射到需要筛选的区间

2. 映射初始条件 $\max (2\times p,\lfloor {left + p - 1}\div{p} \rfloor \times p)$，每次$+p$即可完成对合数的剔除

3. 注意，存储时为了不爆空间，需要对映射区间取一个左端点的偏移量，以区间长度为上限进行存储

python版本

def getPrimes(n):
    vis = [False]*(n + 1)
    for i in range(2,n+1):
        if vis[i] == False:
            primes.append(i)
        j = 0
        while primes[j]*i <= n:
            vis[primes[j]*i] = True
            if i % primes[j] == 0:
                break
            j += 1


primes = []
getPrimes(50000)
while True:   #无定行输入
    try:
        left,right = map(int,input().split())
        vis = [False]*(1000010) #二次筛
        for p in primes:
            j = max(2*p,(left + p - 1)// p * p)
            while j <= right:
                vis[j - left] = True   #为了节省空间需要加入left偏移量
                j += p

        realPrimes = []
        for i in range(right - left + 1):  #遍历原区间（带有left的偏移量）
            if vis[i] == False and i + left >= 2:
                realPrimes.append(i + left)

        if len(realPrimes) < 2:
            print("There are no adjacent primes.")
        else:
            maxPi = 0
            minPi = 0 
            for i in range(len(realPrimes) - 1):
                d =  realPrimes[i + 1] - realPrimes[i]
                if d < realPrimes[minPi + 1] - realPrimes[minPi]:
                    minPi = i
                if d > realPrimes[maxPi + 1] - realPrimes[maxPi]:
                    maxPi = i

            print("%d,%d are closest, %d,%d are most distant." %(realPrimes[minPi],realPrimes[minPi + 1],
                                                                         realPrimes[maxPi],realPrimes[maxPi + 1]))
    except:
        break