对的连续质数的对数，相差6，例如（23,29）从1至20亿

Question

如何在考虑时间复杂度的情况下，找到从10到20亿之间有6个类似（23,29）的连续质数对的数量（使用任何编程语言，而无需使用任何外部库）？

1. 尝试过eratosthenes的筛子，但要获得连续的素数是挑战

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

这将需要存储从 0 到 sqrt(2000000000) 的所有素数，因此内存方面它不是最佳的，但也许这对你有用？如果你想提高效率，你就必须使用更复杂的筛子。

n = 2000000000
last_prime = 3
prime_numbers_to_test = [2, 3]
result = 0

for i in range(5, n, 2):
    for prime in prime_numbers_to_test:
        # Not prime -> next
        if i % prime == 0:
            break

    else:
        # Prime, test our condition
        if i - last_prime == 6:
            result += 1

        last_prime = i

        if i**2 < n:
            prime_numbers_to_test.append(i)

print(result)

编辑此代码产生 11,407,651 对连续素数的结果，其中 n = 2,000,000,000 的差异为 6