Why is my Sieve of Erasthotenes not working? Python 3

Question

This is my code. I'm trying to make an efficient but simple Sieve of Erasthotenes but when I run the program it just keeps returning integers, however large i put the range. This is in python 3.

lyst = []
for i in range(2, 100):
    print(i)
    lyst.append(i)
count = 2
index = 1
for x in lyst:
    print(str(index) + " : " + str(count))
    if x%count == 0 and x != count:
        lyst.remove(x) #removing all multiples of count
    if max(lyst) == count: #breaks loop if count is the largest prime
        break
    else:
        count = lyst[lyst.index(count)+1] #turns count into next prime
    index += 1 #this is just for me to track how many primes i've found

Why do you compare `count == lyst...`? (And throw away the result.) — Jongware, Jan 22 '17 at 11:25
I'm trying to turn count into the next prime, i.e the next greatest one in the list. Trying to replicate what it says on wikipedia for the sieve: — Anon I Mous, Jan 22 '17 at 11:27
you do realize that you're removing all x's ... not only multiples .. ? — Noctis, Jan 22 '17 at 11:28
@Noctis sorry? I do not see how I am doing that. I thought i put in the and operator and those conditions to only eliminate multiples — Anon I Mous, Jan 22 '17 at 11:29
`==` is a *comparison*, not an assignment. You didn't do `count == 2` either. — Jongware, Jan 22 '17 at 11:30
because the logic should be : take a number, remove all it's multiples from the list, take the next number, rinse and repeat, until you're out of numbers. where in your code do you remove the multiples ? you need a second loop, which you obviously don't have. — Noctis, Jan 22 '17 at 11:33
But @Noctis, am i not removing all the multiples from my code here? if x%count == 0 and x != count: lyst.remove(x) — Anon I Mous, Jan 22 '17 at 11:33
nope, that is for the the x you're working on ... so, for each element of the list ...(which you misspelled as lyst, but let's not be petty). what you want, is after taking a number, add it to your primes, and remove all it's duplicates — Noctis, Jan 22 '17 at 11:38
No the reason I "misspelt" list as lyst is because I like it as my listname. But thanks anyway — Anon I Mous, Jan 22 '17 at 11:40
so many fine answers, yet you have not commented on any ... :( — Noctis, Jan 23 '17 at 00:44

score 1 · Answer 1 · edited May 23 '17 at 11:45

The value for x and count will always have the same value:

they start out like that with value 2
for this reason the remove will not be executed
at the end of the iteration count will be the next value from the list, which is exactly what x will be at the start of the next iteration

Conclusion: they have the same value at the start of each iteration, and therefore the if condition is never satisfied.

Secondly, the sieve of Erasthotenes is not supposed to remove elements from the sieve, but to mark certain values as non-prime. Its power is in keeping the values at their original index, so .remove() is not really supposed to occur in a plain sieve algorithm.

For inspiration on finding a correct implementation, you can look at several answers:

Sieve of Eratosthenes - Finding Primes Python
A Fast Prime Number Sieve in Python
Python- Sieve of Eratosthenes- Compact Python
... and a whole lot more.

score 0 · Answer 2 · answered Jan 22 '17 at 11:51

This should do it ... have a look at the inner loop that removes the multiples:

lyst = []
max = 100 # because ... you know, variables. ...
for i in range(2, max):
    lyst.append(i)
count = 2
index = 1
for x in lyst:
    print(str(index) + " : " + str(x)) # x is a prime number, so print it
    for y in lyst:
        if y>x and y%x == 0:
            lyst.remove(y)

    index += 1 #this is just for me to track how many primes i've found
print(index) # how many did we find

Eric Duminil · Answer 3 · 2017-01-27T17:08:30.433

0

This is a mix of your code and the wikipedia description :

n = 100
lyst = range(2, n)
for p in lyst:
    if not p:
        continue
    for i in range(2*p,n,p):
      lyst[i-2] = None
print [p for p in lyst if p]
#=> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

edited Jan 27 '17 at 17:08

answered Jan 22 '17 at 11:54

Eric Duminil

52,989
9
71
124

1

Wikipedia description goes to great lengths repeating over and over that the multiples are to be generated at equal increments (i.e. by repeated additions), ***not*** found by any divisibility tests. – Will Ness Jan 27 '17 at 16:51
@WillNess : Excellent comment, thanks. It's often harder to modify an existing script than starting from scratch. I updated the method. – Eric Duminil Jan 27 '17 at 17:09
glad to be of help. :) – Will Ness Jan 27 '17 at 19:20

Why is my Sieve of Erasthotenes not working? Python 3

3 Answers3