Erathostenes sieve optimization [duplicate]

Question

I've written the erathostenes algorithm in python a few weeks ago, and it looked like the following:

def erathostenes(n):

    A = range(2,n+1)
    B = []
    i = 0

    while A[i] < math.sqrt(n):
        B.append(A[i])
        j = i
        aux = A[i]
        while j < len(A):
            if A[j]%aux == 0:
                A[j] = 0
            j += aux
        i += 1
        while A[i] == 0:
            i +=  1
    for i in range(len(A)):
        if A[i] != 0:
            B.append(A[i])
        i += 1
    return B

After thinking a little (I'm noob in programming) i just did some modifications in my algorithm an right now looks like:

def erathostenes(n):

    A = range(2,n + 1)
    B = []
    i = 0

    raiz = math.sqrt(n)
    lenA = len(A)       
    rangeLenA = range(lenA)

    while A[i] < raiz:
        B.append(A[i])
        j = i
        aux = A[i]

        while j < lenA:
            A[j] = 0
            j += aux
        i += 1
        while A[i] == 0:
            i +=  1
    for i in rangeLenA:
        if A[i] != 0:
            B.append(A[i])
        i += 1
    return B

If I execute the algorithm with n=10.000.000 the execution time in the first code is approximately 7 sec and with the second code it's about 4 seconds.

Any ideas about some more optimizations in my algorithm? thanks!

Answer 1

i += 1 

in the last loop is funny.

Consider replacing

for i in rangeLenA: 

with

for i in xrange(LenA) 

you avoid generating a huge list you don't need.

EDIT:

Also consider this:

    for j in xrange(i,lenA,aux):

instead of:

    while j < lenA:

And fix the bug

while A[i] <= raiz: 

as suggested by fryday.

Answer 2

There is a error in your code. Change

while A[i] < raiz:

on

while A[i] <= raiz:

You can found error when N is square.

For opimization use xrange for rangeLenA instead of range.