CODEWITHSUNDEEP
pythonprimessieve-of-eratosthenes
user637965
user637965

Reputation:

value error for seive of eratosthenes problem in python

Here's my version of the Sieve of Eratosthenes for finding prime numbers up to a limit n. I feel like it should work but I get an error and I don't really understand why:

    mylist.remove(i)
ValueError: list.remove(x): x not in list

Why does it mention x?

Here's the code:

def number_list(n):

    mylist = []
    for i in range(2,n+1):
        mylist.append(i)
    return mylist


def sieve():

    n = eval(input("What is the maximum limit? "))
    mylist = number_list(n)

    primes = []

    for i in mylist:
        p = mylist.pop(0)
        primes.append(p)
        if i % p == 0:
            mylist.remove(i)
    return primes

Upvotes: 0

Views: 226

Answers (4)

halex
halex

Reputation: 16403

Here is a working code for the Sieve of Eratosthenes. The range object must be made to a list because we need to delete items. 

def all_primes_to(n):
    numbers = list(range(2,n+1))
    primes = []
    while numbers:
        prime = numbers.pop(0)
        primes.append(prime)
        remove_multiples(numbers, prime)
    return primes

def remove_multiples(lst, x):
    length = len(lst)
    i = 0
    while i < length:
        if lst[i] % x == 0:
            del lst[i]
            length -= 1
        i += 1

Upvotes: 1

Sven Marnach
Sven Marnach

Reputation: 602105

You are modifying mylist while iterating over it. This will yield strange results. During the first run of your loop, i will be assigned the first item of your list, i.e. 2. Then, the statement

p = mylist.pop(0)

removes this very item from the beginning of the list, and p is also set to 2. Next, your check i % p == 0 will yield True, and you try to remove i from the list, but it is already gone, resulting in the error message you cited.

The complete logic of this loop seems to be broken. For each prime you encounter, you need to remove all multiples of that prime from the list. You usually need two nested loops to achieve this.

Furthermore, your function

def number_list(n):
    mylist = []
    for i in range(2,n+1):
        mylist.append(i)
    return mylist

is equivalent to

def number_list(n):
    return range(2, n + 1)

i.e. you would not need this function at all, just use range(2, n + 1) instead.

Upvotes: 2

Wolph
Wolph

Reputation: 80061

The specific x mentioned here is actually i (as seen on the line above).

Stacktraces normally also give you line numbers so it should be easy to debug knowing that.

Either way, the problem here is that you are trying to remove some items more than once. You can easily fix it with a if i in mylist but I recommend you look at a complete implementation of the sieve to get a faster/more optimized (and more importantly, working) version. It might give you some extra insight on how Python works.

Upvotes: 0

bua
bua

Reputation: 4880

Not sure but i think you shouldn't modify list you're iterating over.
It's forbidden in perl, maybe python is similar in this case.

Another thing is that I would use generators for your all item list.
Approach you're using will blow memory for big 'n's.

Upvotes: 0

Related Questions