Sieve Of Eratosthenes (Still on Prime)
[caption id="attachment_660" align="alignnone" width="246"]
Sieve of Eratosthenes[/caption] I could not make my code any better so I decided that I new approach needed to be found... Boom Eratosthenes came to the rescue. I found those two great web sites: Sieve Of Eratosthenes explained and
Sieve Of Eratosthenes code.
In the second link I found a bit of code that run 10^7 in few seconds, with my old code to get a 10^8 with multi treading took few days! Shocked is the word I will used! Below is the beauty I found!
from numpy import array, bool_, multiply, nonzero, ones, put, resize
#
def makepattern(smallprimes):
pattern = ones(multiply.reduce(smallprimes), dtype=bool_)
pattern[0] = 0
for p in smallprimes:
pattern[p::p] = 0
return pattern
#
def primes_upto3(limit, smallprimes=(2,3,5,7,11)):
sp = array(smallprimes)
if limit <= sp.max(): return sp[sp <= limit]
#
isprime = resize(makepattern(sp), limit + 1)
isprime[:2] = 0; put(isprime, sp, 1)
#
for n in range(sp.max() + 2, int(limit**0.5 + 1.5), 2):
if isprime[n]:
isprime[n*n::n] = 0
return nonzero(isprime)[0]
def main(): print(list(primes_upto3(10**7, smallprimes=primes_upto3(15))))
if __name__=="__main__": main()
This code is not just massively faster then my approach but way smarter! I hope this will take me nearer to my BIG prime!