CODEWITHSUNDEEP
pythonsieve-of-eratosthenes
flybonzai
flybonzai

Reputation: 3941

Sieve of Eratosthenes loop not correctly pulling elements

I'm using a Sieve of Eratosthenes algorithm that involves pulling the first element from a list, adding it to a list of primes, and then pulling out any multiples of that number from the original list (so starting at 2, append 2, remove all multiples of 2). Then on to the next number.

My loop (in a test run on a list of 2-10) does what it's supposed to the first time around, but instead of pulling 3 the next time, it jumps straight to 5 and I'm left with a list of 2, 5, and 9. Here is my code.

list_before_primes = [num for num in range(2, usr_in + 1)]
print(list_before_primes)
list_o_primes = []

for element in list_before_primes:
    list_o_primes.append(element)
    for sub_element in list_before_primes:
            if sub_element % element == 0:
                list_before_primes.remove(sub_element)

print(list_o_primes)

Upvotes: 0

Views: 66

Answers (2)

kmad1729
kmad1729

Reputation: 1614

Here is an implementation of the algorithm:

def sieve_of_eratosthenes(usr_in):
    #you don't need list comprehension in your implementation. You can do this:
    list_before_primes = range(2, usr_in + 1)
    print(list_before_primes)

    #makes a set of list_before_primes
    #funny things can happen when you modify and iterate over the list at the same time. 
    #it is better to make a copy and remove from it.
    list_o_primes = set(list_before_primes)

    for i,element in enumerate(list_before_primes):
        for sub_element in list_before_primes[i+1:]:
            if sub_element % element == 0:
                if sub_element in list_o_primes:
                    list_o_primes.remove(sub_element)

    print(list_o_primes)

if __name__ == '__main__':
    sieve_of_eratosthenes(10)

Upvotes: 0

oliverpool
oliverpool

Reputation: 1671

Since you modify the list_before_primes inside the loop, you shouldn't use for element in list_before_primes: (as noted by @Kevin).

You can use a while list_before_primes: instead and pop the first item into element.

This will also solve @Kashyap Maduri remark (since the element will be removed from the list).

btw, you can simplify list_before_primes = [num for num in range(2, usr_in + 1)] with list_before_primes = list(range(2, usr_in + 1))

Upvotes: 2

Related Questions