Python Sieve of Eratosthenes not working

Question

First of all, this is HOMEWORK, I am currently working on a Sieve of Eratosthenes on python. My program looks like:

x=[]
    for i in range(2,100):
        x.append(i)
primes=[]
i=2

while len(x)!=0:
    k=x[0]
    x.pop(0)
    primes.append(k)
    while k*i in x:
        x.remove(k*i)
        i+=1

print(primes)
print(x)

When my program prints for 'primes', I get:

[2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39,
41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77,
79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99]

Why are there composite numbers in the list? It looks like the program should work

#

Edited the program, now it looks:

x=[]
for i in range(2,100):
    x.append(i)
primes=[]



while len(x)!=0:
    i=2
    k=x[0]
    x.pop(0)
    primes.append(k)
    while k*i<=max(x):
        x.remove(k*i)
        i+=1
        if k*i not in x:
            i+=1

print('primes','\n',primes,sep='')
print('x','\n',x,sep='')

Still not working, getting an error; "ValueError: list.remove(x): x not in list"

Answer 1

One problem is you only ever add to i. You need to reset i back to 2 every time you pop another element from the list.

That is, at first you pop 2 from the list. You gradually increase i to remove all multiple of 2 from the list. At the end of this, i will be 50. But then you go back and pop 3 from the list, and i is still 50, so it only looks for 50*3 in the list.

Even if you fix this, though, it still won't work, because you stop looking at i values as soon as you find one that isn't in the list. But it's possible that k*i isn't in the list but k*(i+1) is -- for instance, after you seive multiples of 2, the first multiple of 3 (namely 6) isn't in the list, but the next (namely 9) is. So you can't stop until you try every multiple up to the list max.