Python 3: Why is my prime sieve so slow? I've implemented the sieve of Eratosthenes in Python 3 as follows:

def sieve_of_eratosthenes(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    p = 0

    while True:        
        for i, prime in enumerate(is_prime):
            if prime and i &gt; p:
                p = i
                break
        else:
            break

        multiple = p + p

        while multiple &lt;= n:
            is_prime[multiple]= False
            multiple = multiple + p

    r = []
    for i, prime in enumerate(is_prime):
        if prime: r.append(i)
    return r


Running this to 100,000 takes ~25 seconds. 

I felt that was on the slow side, so I decided to take a different approach. The Sieve works prospectivly: it works ahead to clear out all multiples. I made a retrospective function, trial-dividing everything lower than the current prime-candidate:

def retrospect(n):
    primes = [2, 3]
    i = 5

    while i &lt;= n:
        isprime = True
        lim = math.sqrt(n)+1
        for p in primes:
            if p &gt; lim:
                break
            if i % p == 0:
                isprime = False
                break
        if isprime:
            primes.append(i)
        i += 2

    return primes


This is way faster!

Questions:


Are there any obvious shortcomings to the Sieve implementation?
Is there a point where the retrospect gets slower than the sieve?
while True:        
        for i, prime in enumerate(is_prime):
            if prime and i &gt; p:
                p = i
                break
        else:
            break



This is the cause of the slowness: track the state between loops and the 25 seconds drop to 0.05 seconds.




        multiple = p + p

        while multiple &lt;= n:
            is_prime[multiple]= False
            multiple = multiple + p



It's probably more Pythonic to use range here:

        for multiple in range(p + p, n + 1, p):
            is_prime[multiple] = False


When handling larger inputs, it becomes worthwhile starting at p * p instead of p + p (on the basis that every composite multiple of p smaller than p * p also has a smaller prime factor).




    r = []
    for i, prime in enumerate(is_prime):
        if prime: r.append(i)
    return r



IMO it makes more sense to inline this into the main loop.



Edited code at this point:

def sieve_of_eratosthenes(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False

    primes = []

    for p in range(2, n+1):
        if is_prime[p]:
            primes.append(p)

            for multiple in range(p * p, n + 1, p):
                is_prime[multiple] = False

    return primes




Now if you want more speed at the cost of complicating things ever so slightly, you can apply a simple wheel by special-casing the only even prime:

def sieve_of_eratosthenes(n):
    is_prime = [True] * (n+1)
    primes = [2]

    for p in range(3, n + 1, 2):
        if is_prime[p]:
            primes.append(p)

            for multiple in range(p * p, n + 1, p + p):
                is_prime[multiple] = False

    return primes