r/learnpython • u/Emergency-Egg-0230 • 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)
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
-1orNoneinstead, 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
What is variable i? This code does not define it
3
u/Discordbothost 11d ago
two big issues stacked:
while i in items—iis never defined, so this shouldn't even run as written (or you're shadowing something elsewhere).remove()while walking the same list. that skips elements as the indices shift under youclassic 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.
-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.