HiveBrain v1.2.0
Get Started
← Back to all entries
patternpythonMinor

Sieve of Eratosthenes solution for CodeEval

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
codeevalsieveforsolutioneratosthenes

Problem

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)

Solution

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)

Code Snippets

A[0] = 0
A[1] = 0
for i in xrange(2, int(math.sqrt(n))):
for j in xrange(i ** 2, n + 1, i):
return [i for i in A if i != 0]
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)

Context

StackExchange Code Review Q#126517, answer score: 3

Revisions (0)

No revisions yet.