Python 3: Why is my prime sieve so slow?
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