Python 3 - removing elements from a list while iterating (sieve of Eratosthenes)

Question

I am building a program to find all primes smaller than a number n using the algorithm of the sieve of Eratosthenes using python. The algorithm first creates a list of numbers from 2 to n, then iterates over the list removing the first element available and the corresponding multiples. The problem is that I don't seem to get the right result doing this way. I would also appreciate any suggestion to improve the performance.

This is the algorithm:

def primes(max):
    '''The sieve of Eratosthenes
    Algorithm to find all primes smaller than max'''
    init = time.clock()
    allNum = [a for a in range(2, max+1)]
    primes = []
    for n in allNum:
        # remove all multiples of prime n
        toRemove = (a for a in range(n, max+1, n) if a in allNum)
        for i in toRemove:
            print('toRemove:', i)
            allNum.remove(i)
        # add the prime to the list
        primes.append(n)

    deltaT = time.clock() - init
    print('Time taken to process:', deltaT)
    return primes

(SOLVED) This is how I changed it:

while len(allNum) != 0:
    prime = allNum[0]
    # remove all multiples of prime
    toRemove = (a for a in range(prime, max+1, prime) if a in allNum)
    for i in toRemove:
        print('toRemove:', i)
        allNum.remove(i)
    # add the prime to the list
    primes.append(prime)

Possible duplicate of [strange result when removing item from a list](https://stackoverflow.com/questions/6260089/strange-result-when-removing-item-from-a-list) — roganjosh, Aug 31 '18 at 19:33

T Burgis · Answer 1 · 2018-08-31T22:07:59.237

An alternative which is quicker is to build a list of booleans (all True) and set them to False using the algorithm. The primes are all the indices in the list that remain true:

def primes(max):
    mask = [True for i in range(0,max + 1)]
    for num in range(2,max):
        if not mask[num]:
            continue
        for multiple in range(num*2, max+1, num):
            mask[multiple] = False
    primes = [i for i,mask_value in enumerate(mask) if mask_value]
    return primes[2:]

score 0 · Answer 2 · answered Aug 31 '18 at 19:59

When you iterate over a list, you are referencing each offset, not each value. For example, when you get the first result, if it qualifies and removes the value, all of the subsequent values slide forward and your offset increments. Your offset is now index 1 (base 0). But you just removed index 0 and everything slid forward. You essentially skipped the second number.

0$ python3
Python 3.4.8 (default, Mar 23 2018, 10:04:27)
[GCC 4.8.5 20150623 (Red Hat 4.8.5-16)] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> [a for a in range(1, 20)]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
>>> the_list = [a for a in range(1, 20)]
>>> for a in the_list:
...     the_list.remove(a)
...
>>> the_list
[2, 4, 6, 8, 10, 12, 14, 16, 18]
>>>

score -1 · Accepted Answer · answered Aug 31 '18 at 19:37

-1

I don't believe you can alter a list as you iterate over it.

You could switch to a while loop, that runs so long as any numbers are left in your original list. For every iteration, you remove at least the first number: if it is prime you move it to your prime list, if it is not you remove it and all its multiples.

answered Aug 31 '18 at 19:37

ScottieB

3,958
6
42
60

That's still modifying a list while iterating over it? – roganjosh Aug 31 '18 at 19:40
1

@roganjosh no it is not iterating over it in the while loop because it's just verifying that there are still items in it – BONANDRINI CARLO Aug 31 '18 at 19:50
But that would require scanning the entire list each time? – roganjosh Aug 31 '18 at 19:51
@roganjosh in which part of the program? because it always has to scan it when creating the toRemove list – BONANDRINI CARLO Aug 31 '18 at 19:58
3

You can modify a list while iterating through it as he is. See my answer below demonstrating it. Some scenarios do not allow it, but this is not one such scenario. – UtahJarhead Aug 31 '18 at 20:25

Python 3 - removing elements from a list while iterating (sieve of Eratosthenes)

3 Answers3