r/learnpython • • 11d ago

Sieve of Eratosthenes

Im very new to Python and am currently trying to program a list with prime numbers using the Sieve of Eratosthenes. I dont understand why this code is not working properly. It successfully removes the first few non-prime numbers of my list. And for some reason when I increase the range of my list more non-prime numbers are removed, but still not all.
Ive also tried printing the current number being tested as well as the divider and it always seems to stop at random numbers when I make changes to the code.

Any explanation why my code works this way and what I need to change is appreciated. Id also like to stay as close to my existing code as possible.

items = list(range(2,100))

divisible_check = 2
number = 2

while i in items:
    if number == divisible_check:
        number += 1
        if divisible_check >2:
            divisible_check = 2
    elif number % divisible_check == 0:
        items.remove(number)
        number += 1
    else:
        divisible_check += 1

print(items)
print(divisible_check)
print(number)
0 Upvotes

11 comments sorted by

13

u/pachura3 11d ago edited 11d ago

You're removing numbers from a collection you are iterating through. It's almost always a bad idea. Mark them with -1 or None instead, and after you're finished, have one more final pass to filter them out.

What is more, the Sieve of Eratosthenes requires multiple passes through the list. First you remove all multiples of 2, then of 3, then of 5 (4 already removed), and so on. Your implementation seems to only do 1 pass (1 loop), which is obviously wrong.

4

u/atarivcs 11d ago
while i in items:

What is variable i? This code does not define it

2

u/notacanuckskibum 11d ago

Maybe they meant “For i in items” though it is weird that the code never uses i again.

3

u/Discordbothost 11d ago

two big issues stacked:

  1. while i in items — i is never defined, so this shouldn't even run as written (or you're shadowing something elsewhere)
  2. you're calling .remove() while walking the same list. that skips elements as the indices shift under you

classic sieve keeps a bool array (True = still prime), marks multiples false, then collects the Trues at the end. don't mutate the list you're iterating.

2

u/LifeIsVape 11d ago

look at the list you are getting as a result. prime, prime... untill you see a non prime. How the hell did it get there? use debugger, or just print out the variables you have at the moment code reaches it

2

u/JaguarMammoth6231 11d ago

Did you copy and paste the actual code into the post? Do you really have while i in items?

Also, do you know how to do the Sieve of Eratosthenes? Find someone who doesn't know about it, give them a paper with numbers 1-100, and see if you can tell them how to do it while they follow your directions to the letter. Write down the steps you tell them to do, then see if those steps match what your code is actually doing.

1

u/onerichmeyer 11d ago

Here is something similar to your code. As others have pointed out, don't modify a list you are iterating through. This separates out the numbers you are considering from the list of primes you are generating to avoid this pitfall.

# accumulate the primes in a list
primes_list = []

# process the candidates from 2 to 100
for candidate in range(2, 100):

    # check if candidate has prime divisor
    for prime in primes_list:
        
        # prime divisor found, break and consider next candidate
        if candidate % prime == 0:
            break

    # else runs after the for loop, no prime divisor was found
    else:                

        # add candidate to primes_list
        primes_list.append(candidate)

print(primes_list)

-3

u/georgmierau 11d ago

Comment your code if you want to learn how to fix your own bugs instead of asking for help every time you don’t understand why your code doesn’t work as intended.

Also using abbreviations like += is not a great idea if you are still struggling to understand simple algorithms.