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?
Tried sieve of eratosthenes but getting consecutive primes is challenge
Used generators but time complexity is very high
The code is:
def gen_numbers(n):for ele in range(1,n+1):for i in range(2,ele//2):if ele%i==0:breakelse:yield eleprev=0count=0for i in gen_numbers(2000000000):if i-prev==6:count+=1prev = i
Interesting question! I have recently been working on Sieve of Eratosthenes prime generators. @Hans Olsson says
You should use segmented sieve to avoid memory issue:en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Segmented_sieve
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.
The code:
#!/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-Eratosthenesimport sysdef segmentedSieve(limit):sqrt = int(limit ** 0.5)segment_size = sqrtprev = 0count = 0# we sieve primes >= 3i = 3n = 3sieve = []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 offwhile i * i <= high:if is_prime[i]:primes.append(i)multiples.append(i * i - low)two_i = i + ifor j in xrange(i * i, sqrt, two_i):is_prime[j] = Falsei += 2# sieve the current segmentfor x in xrange(len(primes)):k = primes[x] * 2j = multiples[x]while j < segment_size: # NB: "for j in range()" doesn't work here.sieve[j] = Falsej += kmultiples[x] = j - segment_size# collect results from this segmentwhile n <= high:if sieve[n - low]:out_primes.append(n)if n - 6 == prev:count += 1diff6.append(n)prev = nn += 2print count, "prime pairs found with a difference of 6."if limit < 1000:for x in diff6:print "(", x-6, ",", x, ")",printreturn 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
This might work as-is if you run it for size 2e9 (2 billion) and subtract the result of size 1e9 (1 billion).
EDIT
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
... on my newish laptop, 1.6 GHz i5-8265U, 8G RAM, Ubuntu on WSL, Win10
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