Sieve of Eratosthenes in Python, looking for a more condensed and correct solution to finding primes

Question

I developed a prime generator using the Sieve of Erasothenes method. Using a list, I eliminate all multiples of 2 up to a user-designated number, continuing with 3, etc. My code is currently giving me a error due to the fact that p2 is being reassigned to the first element of the list indefinitely.

n = int(input("What are the primes up to this number?"))
soe = []
for i in range (2, n+1):
    soe.append(i)
for i in range (2, n+1):
    if i % 2 == 0:
        soe.remove(i)
    p2 = soe[0]
    holder =1
while p2 < n and holder == 1:
    for i in soe:
        if i % p2 == 0:
            soe.remove(i)
    p2 = soe[0]
print (soe)

Answer 1

Here is a simpler and quicker Sieve generator in Python:

maxPrime = int(input("What are the primes up to this number?"))
sieve = list(range(maxPrime))
for i in range(2, maxPrime):
    if sieve[i]: # not removed yet = prime!
        print(i)
        for product in range(i, maxPrime, i): # gets i*n for all n up to i*n > maxPrime
            sieve[product] = 0 # marked as not prime

The problem in your code is that you always assign p2=soe[0]. Additionally, at the end, you print soe, when you have already removed everything from it.

You should print every new p2 you use, including 2, and end the program when soe is empty.

Here is your modified program that is working, with comments:

n = int(input("What are the primes up to this number?"))
soe = []
for i in range (2, n+1):
    soe.append(i)
# you can progress straight into sieving out numbers!
while p2 < n and soe: # stop when your list is empty!
    p2 = soe[0]
    print(p2)
    for i in soe:
        if i % p2 == 0:
            soe.remove(i)
# print (soe) # it's going to be empty at the end

Answer 2

I use this:

def eras(n):
    last = n + 1
    sieve = [0, 0] + list(range(2, last))
    sqn = int(round(n ** 0.5))
    it = (i for i in xrange(2, sqn + 1) if sieve[i])
    for i in it:
        sieve[i * i:last:i] = [0] * (n // i - i + 1)
    return filter(None, sieve)

The real magic is in the slice-assignment in the for-loop. It zeroes out the non-primes from i * i to n in one go.

Answer 3

An large performance improvement (at least for cpython) to @icedtrees answer is to set the terms to zero at the C-level using a slice assignment.

maxPrime = int(input("What are the primes up to this number?"))
sieve = list(range(maxPrime))
for i in range(2, maxPrime):
    if sieve[i]: # not removed yet = prime!
        print(i)
        sieve[::i] = [0] * len(sieve[::i]) # marked as not prime

You can instead use

        sieve[i::i] = [0] * ((len(sieve)-1)//i)

for the last line if you prefer.

I haven't tried it, but pypy probably does a decent job of optimising the inner for loop compared to the slice assignment regardless.