A Sieve of Eratosthenes

Question

I have written this Sieve of Eratosthenes. This is a bit of software that will find all of the prime numbers between 2 and n, where n is a user-defined value.
The code does seem quite bloated and any help at making it more elegant would be great. I know that I am not very good at list comprehensions and if it is possible to utilise them more in this situation I would love to know how.
def sieve_of_eratosthenes(n):
    """
    Create a Sieve of Eratosthenes to find all of the prime
    numbers between 2 and n
    """
    n += 1

num_list = []
    [num_list.append(i) for i in range(2, n)]

test = 0
    while test < len(num_list):
        for i, x in enumerate(num_list):
            if num_list[i] % num_list[test] == 0:
                if num_list[i] != num_list[test]:
                    del num_list[i]
        test += 1
    return num_list

Zachary Vance · Answer

Agreed, this is not the Sieve of Eratosthenes. This is trial division by primes. (As long as you're doing trial division, you can do it slightly better, and only test up to the square root of the number.)
Replace the while loop, making it clearer and more pythonic: for test in num_list:
It is inefficient to delete from the middle of a list in python, which takes O(n) time.
It is generally unsafe, and will give wrong results to delete from an collection WHILE iterating through it. In this case it seems to work, but be careful. I would instead keep a binary flag for each number, with whether we've found a factor already or not (array of True/False).

A Sieve of Eratosthenes

One Answer

Add your own answers!

Ask a Question