The Sieve Function. Need Help!!!

[br0wnm4n]

Hi, I am having some trouble writing this code. The question is as follows:

The Sieve of Erastophenes is an algorithm -- known to ancient greeks -- that finds all prime numbers up to a given number n. It does this by first creating a list L from 2 to n and an (initially) empty list primeL. The algorithm then takes 2 (the first number in list L) and appends it to list primeL, and then removes 2 and all its multiples (4,6,8,10,12, ...) from L. The algorithm then takes 3 (the new first number in L) and appends it to list primeL, and then removes 3 and all its remaining multiples (9,15,21,...). So, in every iteration, the first number of list L is appended to list primeL and then it and its multiples are removed from list L. The iterations stop when list L becomes empty. Write a function sieve that takes as input a positive integer n, implements the above algorithm, and returns a list of all prime numbers up to n.

Usage:
>>> sieve(56)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53]
>>> sieve(368)
[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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367]
>>> sieve(32)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]

So far my code for this program looks like this:

def sieve(n):
  lst = []
  for number in range(2,n+1):
    lst.append(number)
  prime = []
  while len(lst) != []:
    prime.append(lst[0])
    lst.pop(0)
  for value in lst:
    if value % prime[-1] == 0:
      lst.remove(value)
  return prime

It keeps giving me an error: 'lst out of range'.

Can someone please help me with this code?

[woooee]

Since "lst" is used on 5 lines of the code, there is no way to tell where the error is. General comments would be the list "prime" is an exact copy of "lst" and so you return a copy of the initial "lst" list. Also, print len(lst) before this statement
while len(lst) != []:
so you know what is being compared to what. And print "lst", "prime" and anything else along the way so you know what is inside the container. There is a lot of testing to be done here. For future posts, test first and post the complete error message.

[TrustyTony]

This algorithm does not use modulo function but step of for loop check your algorithm!

[slate]

A little self promotion might not be wrong.

[TrustyTony]

Yes there is many posts about Erathotenes sieve here in Daniweb, including some mine

However the formulation here is different to that of the optimized version, which consider primes marking from prime*prime until max_prime ** 0.5, and only use Truth value vector.

So it is still not possible to copy those solutions, even the most unoptimized versions. Task is describing different way to do the same thing less efficiently and probably in more original form.

Still I would say that I would use still third list with every nth number range(n,maxprime//n+1,n) to select numbers to remove from second list instead of the modulo.

Of course with liberal interpretation of the description of task, the modern algorithm could be considered correct solution.