对的连续质数的对数，相差6，例如(23,29)从1到20亿 [英] No of Pairs of consecutive prime numbers having difference of 6 like (23,29) from 1 to 2 billion

问题描述

在考虑时间复杂度的情况下，如何查找从1到20亿之间有6个像(23,29)之差的连续质数对的数量(使用任何编程语言，而无需使用任何外部库)?

How to find number of pairs of consecutive prime numbers having difference of 6 like (23,29) from 1 to 2 billion (using any programming language and without using any external libraries) with considering time complexity?

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

1. Tried sieve of eratosthenes but getting consecutive primes is challenge

使用过发电机，但是时间复杂度很高

Used generators but time complexity is very high

代码是:

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

推荐答案

有趣的问题！我最近一直在研究Eratosthenes素数发生器的筛网. @汉斯·奥尔森说

Interesting question! I have recently been working on Sieve of Eratosthenes prime generators. @Hans Olsson says

您应该使用分段筛来避免内存问题: en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Segmented_sieve

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

我同意，并且碰巧有一个我被破解来解决这个问题的人.对于长度和非Pythonic-ness提前致歉.样本输出:

I agree, and happen to have one which I hacked to solve this question. Apologies in advance for the length and non Pythonic-ness. Sample output:

$ ./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亿)的结果，这可能会按原样工作.

This might work as-is if you run it for size 2e9 (2 billion) and subtract the result of size 1e9 (1 billion).

编辑

性能信息，由@ValentinB请求.

Performance info, requested by @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

... on my newish laptop, 1.6 GHz i5-8265U, 8G RAM, Ubuntu on WSL, Win10

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

I found a mod 30 prime wheel here in a comment by Willy Good that is about 3x faster than this code at 1e9, about 2.2x faster at 2e9. Not segmented, the guts is a Python generator. I'm wondering if it could be segmented or changed to use a bit array to help its memory footprint without otherwise destroying its performance.

END EDIT

这篇关于对的连续质数的对数，相差6，例如(23,29)从1到20亿的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！