python - 相差 6 的连续质数对的数量，例如 (23,29) 从 1 到 20 亿

Question

如何在考虑时间复杂度的情况下找到从 1 到 20 亿(使用任何编程语言且不使用任何外部库)相差 6 的连续质数对的数量，例如 (23,29)？

1. 尝试过埃拉托色尼筛法，但获得连续素数是一项挑战

2. 使用了生成器但是时间复杂度很高

代码是:

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

Answer 1

有趣的问题!我最近一直在研究 Eratosthenes 素数生成器的筛法。 @Hans Olsson 说

You should use segmented sieve to avoid memory issue: en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Segmented_sieve

我同意，并且碰巧有一个我破解来解决这个问题的。提前为长度和非Pythonic-ness道歉。示例输出:

$ ./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，WSL 上的 Ubuntu，Win10

我找到了一个 mod 30 主轮 here在 Willy Good 的评论中，在 1e9 时比此代码快约 3 倍，在 2e9 时快约 2.2 倍。没有分段，胆量是一个 Python 生成器。我想知道是否可以对其进行分段或更改以使用位数组来帮助其内存占用，而不会以其他方式破坏其性能。

结束编辑