Ошибка в значении для множества проблем эратосфена в питоне

Question

Вот моя версия Решета Эратосфена для нахождения простых чисел до предела n. Я чувствую, что это должно работать, но я получаю ошибку, и я не понимаю, почему:

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

Почему упоминается х?

Вот код:

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

Answer 1

Вы изменяете mylist, перебирая его.Это даст странные результаты.Во время первого запуска вашего цикла, i будет назначен первый элемент вашего списка, то есть 2.Затем оператор

p = mylist.pop(0)

удаляет этот самый элемент из начала списка, а p также устанавливается на 2.Затем ваш чек i % p == 0 даст True, и вы попытаетесь удалить i из списка, но он уже исчез, в результате чего вы получите сообщение об ошибке, которое вы цитировали.

Полная логика этогопетля, кажется, разорвана.Для каждого простого числа, с которым вы столкнетесь, вам нужно удалить из списка все кратные этого простого числа.Обычно для этого вам нужны два вложенных цикла.

Кроме того, ваша функция

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

эквивалентна

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

, то есть вам вообще не понадобится эта функция, просто используйте range(2, n + 1) вместо.

Answer 2

Вот рабочий код сита Эратосфена. Объект диапазона должен быть внесен в список, потому что нам нужно удалить элементы.

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

Answer 3

Конкретный x, упомянутый здесь, на самом деле i (как видно на приведенной выше строке).

Как правило, стековые трассировки также дают вам номера строк, поэтому отладку будет легко знать, зная это.

В любом случае, проблема в том, что вы пытаетесь удалить некоторые элементы более одного раза.Вы можете легко исправить это с if i in mylist, но я рекомендую вам взглянуть на полную реализацию решета, чтобы получить более быструю / более оптимизированную (и что еще более важно, работающую) версию.Это может дать вам дополнительное представление о том, как работает Python.

Answer 4

Не уверен, но я думаю, что вы не должны изменять список, по которому вы перебираете.
Это запрещено в Perl, возможно, Python похож в этом случае.

Другое дело, что я бы использовал генераторы для всего вашего списка предметов.
Подход, который вы используете, взорвет память для больших чисел.