Sieve of Eratosthenes solution for CodeEval

Question

The code below takes integer n as input, and delivers a list of all primes up to integer n using the Sieve of Eratosthenes.

My question is, could you please help me optimize this code? Is it considered poor code to use 'try' flow control? I'd like to optimize the code such that I don't need it.

def factorfinder(n):
    A = range(0,n+1)
    for i in xrange(0,int(math.sqrt(n))):
        if i == 0 or i == 1:
            A[i] = 0
            continue
        for j in xrange(0,n):
            try:
                A[i**2+j*i] = 0
            except IndexError:
                pass
    return filter(lambda x: x != 0, A)

Answer 1

Your if statement can be moved out of the loop, if you do you need to change the range to start at 2.

A[0] = 0
A[1] = 0
for i in xrange(2, int(math.sqrt(n))):

For your other loop, we can think of the algorithm slightly differently. You start at i ** 2, you take a step of i, and it ends on len(A) (shown by the try-except). Or:

for j in xrange(i ** 2, n + 1, i):

As for filter you can change it to use bool or None instead of the lambda. Alternately you can change it to a list comprehension:

return [i for i in A if i != 0]

This makes the code simple:

def factorfinder(n):
    A = range(n + 1)
    A[0] = 0
    A[1] = 0
    for i in xrange(2, int(math.sqrt(n))):
        for j in xrange(i ** 2, n + 1, i):
            A[j] = 0
    return filter(bool, A)