python - 没有成对的连续素数有6个像(23,29)那样从1到20亿

在考虑时间复杂性的情况下，如何找到6个（23,29）的连续素数对（使用任何编程语言，不使用任何外部库）从10亿到20亿之间的差异？
尝试过的埃拉托斯坦筛网，但获得连续的素数是一个挑战。
用过的发电机，但时间复杂度很高
代码是：

def gen_numbers(n):
    for ele in range(1,n+1):
        for i in range(2,ele//2):
            if ele%i==0:
                break
        else:
            yield ele
    prev=0
    count=0
    for i in gen_numbers(2000000000):
        if i-prev==6:
            count+=1
        prev = i

最佳答案

有趣的问题！我最近一直在研究埃拉托斯坦主发电机的筛子。@汉斯·奥尔森说
您应该使用分段筛选来避免内存问题：
en.wikipedia.org/wiki/筛网
我同意，而且碰巧有一个我破解的来解决这个问题。为长度和非蟒蛇性提前道歉。样品输出：

$ ./primes_diff6.py 100
7 prime pairs found with a difference of 6.
( 23 , 29 ) ( 31 , 37 ) ( 47 , 53 ) ( 53 , 59 ) ( 61 , 67 ) ( 73 , 79 ) ( 83 , 89 )
25 primes found.
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79,
83, 89, 97]
$ ./primes_diff6.py 1e5
1940 prime pairs found with a difference of 6.
9592 primes found.

代码：

#!/usr/bin/python -Wall
# program to find all primes smaller than n, using segmented sieve
# see https://github.com/kimwalisch/primesieve/wiki/Segmented-sieve-of-Eratosthenes

import sys

def segmentedSieve(limit):

    sqrt = int(limit ** 0.5)
    segment_size = sqrt

    prev = 0
    count = 0

    # we sieve primes >= 3
    i = 3
    n = 3

    sieve       = []
    is_prime    = [True] * (sqrt + 1)
    primes      = []
    multiples   = []
    out_primes  = []
    diff6       = []

    for low in xrange(0, limit+1, segment_size):
        sieve = [True] * segment_size

        # current segment = [low, high]
        high = min(low + segment_size -1, limit)

        # add sieving primes needed for the current segment
        #   using a simple sieve of Eratosthenese, starting where we left off
        while i * i <= high:
            if is_prime[i]:
                primes.append(i)
                multiples.append(i * i - low)

                two_i = i + i
                for j in xrange(i * i, sqrt, two_i):
                    is_prime[j] = False
            i += 2

        # sieve the current segment
        for x in xrange(len(primes)):
            k = primes[x] * 2
            j = multiples[x]

            while j < segment_size:     # NB: "for j in range()" doesn't work here.
                sieve[j] = False
                j += k

            multiples[x] = j - segment_size

        # collect results from this segment
        while n <= high:
            if sieve[n - low]:
                out_primes.append(n)
                if n - 6 == prev:
                    count += 1
                    diff6.append(n)
                prev = n
            n += 2

    print count, "prime pairs found with a difference of 6."
    if limit < 1000:
        for x in diff6:
            print "(", x-6, ",", x, ")",
        print
    return out_primes

# Driver Code
if len(sys.argv) < 2:
    n = 500
else:
    n = int(float(sys.argv[1]))

primes = [2] + segmentedSieve(n)

print len(primes), "primes found."
if n < 1000:
    print primes

如果将它运行到2E9（20亿）大小，并减去1E9（10亿）大小的结果，这可能会起作用。
编辑
性能信息，由@valentinb请求。

$ time ./primes_diff6.py 2e9
11407651 prime pairs found with a difference of 6.
98222287 primes found.

real 3m1.089s
user 2m56.328s
sys  0m4.656s

…在我的新笔记本电脑上，1.6 GHz i5-8265U，8G RAM，Ubuntu on WSL，Win10
我在willy good的评论中发现一个mod 30主轮here比代码1E9快3倍，比代码2E9快2.2倍。不是分段的，而是一个python生成器。我想知道它是否可以被分割或更改为使用位数组来帮助它的内存占用，而不会破坏它的性能。
结束编辑