2
\$\begingroup\$

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
\$\endgroup\$
  • 5
    \$\begingroup\$ That is not the Sieve of Eratosthenes, see e.g. my remarks here: codereview.stackexchange.com/a/194762. The Sieve of Eratosthenes algorithms computes multiples, not remainders. \$\endgroup\$ – Martin R Jul 20 at 13:50
1
\$\begingroup\$

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).

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.