Sieve Of Eratosthenes (Still on Prime)
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!