Sieve of Eratosthenes
Sieve of Eratosthenes

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!

Leave a comment

Your email address will not be published. Required fields are marked *

Time limit is exhausted. Please reload CAPTCHA.