Code: Select all
from itertools import count
from timeit import default_timer
start = default_timer()
# ideone.com/aVndFM
def postponed_sieve(): # postponed sieve, by Will Ness
for c in (2, 3, 5, 7): # original code David Eppstein,
yield c
sieve = {} # Alex Martelli, ActiveState Recipe 2002
ps = postponed_sieve() # a separate base Primes Supply:
p = next(ps) and next(ps) # (3) a Prime to add to dict
q = p*p # (9) its sQuare
for c in count(9, 2): # the Candidate
if c in sieve: # c's a multiple of some base prime
s = sieve.pop(c) # i.e. a composite ; or
elif c < q:
yield c # a prime
continue
else: # (c==q): # or the next base prime's square:
s=count(q+2*p,2*p) # (9+6, by 6 : 15,21,27,33,...)
p=next(ps) # (5)
q=p*p # (25)
for m in s: # the next multiple
if m not in sieve: # no duplicates
break
sieve[m] = s # original test entry: ideone.com/WFv4f
res = 0
for k in postponed_sieve():
if k > 10000000:
break
res += 1
#print(k)
print(res)
print(default_timer() - start)
So my question is WHY? Can anyone point out the reason for this? Especially with the 'mod 30' version, we are checking only 8 out of every 30 numbers, rather than 15 out of every 30 numbers in the 'mod 2' version. Even discounting for certain computing aspects, I expect atleast 25% reduction in time. But no good came out of the modification. I can't understand why.
Mod 6 version
Code: Select all
from itertools import count
from timeit import default_timer
start = default_timer()
def psieve():
for k in (5, 7, 11):
yield k
D = {}
ps = psieve()
p = next(ps)
q = p * p
for temp in count(12, 6):
for j in (1, 5):
k = temp + j
if k in D:
step = D.pop(k)
elif k < q:
yield k
continue
else:
step = 2 * p
p = next(ps)
q = p * p
res = k + step
while res in D or res % 6 not in (1, 5):
res += step
D[res] = step
res = 0
for k in psieve():
if k > 10000000:
break
res += 1
#print(k)
print(res + 2)
print(default_timer() - start)
Code: Select all
from itertools import count
from timeit import default_timer
start = default_timer()
def psieve():
for k in (7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47):
yield k
D = {}
ps = psieve()
p = next(ps)
q = p * p
for temp in count(49, 30):
for j in (0, 4, 10, 12, 18, 22, 24, 28):
k = temp + j
if k in D:
step = D.pop(k)
elif k < q:
yield k
continue
else:
step = 2 * p
p = next(ps)
q = p * p
res = k + step
while res in D or res % 30 not in (1, 7, 11, 13, 17, 19, 23, 29):
res += step
D[res] = step
res = 0
for k in psieve():
if k > 10000000:
break
res += 1
#print(k)
print(res + 3)
print(default_timer() - start)