Петля сита Эратосфена неправильно вытягивает элементы

Я использую алгоритм решета Эратосфена, который включает в себя извлечение первого элемента из списка, добавление его в список простых чисел, а затем извлечение любых кратных этому числу из исходного списка (так что, начиная с 2, добавляйте 2, удаляйте все кратные 2). Потом на следующий номер.

Мой цикл (в тестовом прогоне со списком 2-10) делает то, что он должен делать в первый раз, но вместо того, чтобы вытягивать 3 в следующий раз, он сразу переходит к 5, и у меня остается список из 2, 5 и 9. Вот мой код.

list_before_primes = [num for num in range(2, usr_in + 1)]
print(list_before_primes)
list_o_primes = []

for element in list_before_primes:
    list_o_primes.append(element)
    for sub_element in list_before_primes:
            if sub_element % element == 0:
                list_before_primes.remove(sub_element)

print(list_o_primes)

python sieve-of-eratosthenes
person flybonzai    schedule 08.10.2015    source источник
comment
Непредвиденные вещи могут произойти, когда вы изменяете размер списка во время его повторения.   -  person Kevin    schedule 08.10.2015
comment
Итак, моя логика выглядит здравой? Если это так, то я переработаю алгоритм.   -  person flybonzai    schedule 08.10.2015
comment
у вас есть но в вашем коде. element и sub_element одинаковы в первой итерации. Так что sub_element % element == 0 всегда будет возвращать True   -  person kmad1729    schedule 08.10.2015

Ответы (2)


arrow_upward
2
arrow_downward

Поскольку вы изменяете list_before_primes внутри цикла, вы не должны использовать for element in list_before_primes: (как заметил @Kevin).

Вместо этого вы можете использовать while list_before_primes: и поместить первый элемент в element.

Это также решит замечание @Kashyap Maduri (поскольку элемент будет удален из списка).

Кстати, вы можете упростить list_before_primes = [num for num in range(2, usr_in + 1)] с помощью list_before_primes = list(range(2, usr_in + 1))

person oliverpool    schedule 08.10.2015
comment
В Python 3 range возвращает генератор, а не список. Но list(range(2, usr_in + 1)) работает так же хорошо и проще. - person Mark Ransom; 08.10.2015

arrow_upward
0
arrow_downward

Вот реализация алгоритма:

def sieve_of_eratosthenes(usr_in):
    #you don't need list comprehension in your implementation. You can do this:
    list_before_primes = range(2, usr_in + 1)
    print(list_before_primes)

    #makes a set of list_before_primes
    #funny things can happen when you modify and iterate over the list at the same time. 
    #it is better to make a copy and remove from it.
    list_o_primes = set(list_before_primes)

    for i,element in enumerate(list_before_primes):
        for sub_element in list_before_primes[i+1:]:
            if sub_element % element == 0:
                if sub_element in list_o_primes:
                    list_o_primes.remove(sub_element)

    print(list_o_primes)

if __name__ == '__main__':
    sieve_of_eratosthenes(10)
person kmad1729    schedule 08.10.2015
comment
Это кажется неверным: for i,element in enumerate(list_before_primes): вы собираетесь проверить каждый элемент между 2 и n (когда вы должны проверять только те элементы, которые не были удалены) - person oliverpool; 08.10.2015
comment
вот почему у меня есть if sub_element in list_o_primes:. Не самый оптимальный код, но работает. - person kmad1729; 08.10.2015
comment
Я объяснил все в комментариях к вашему сведению. Я добавляю реализацию на основе комментариев. - person kmad1729; 08.10.2015
comment
Я не думаю, что есть необходимость отрицать ответ. Я предоставил реализацию решения с комментариями. И объяснил идею копирования списка в коде, который будет полезен для плаката. - person kmad1729; 08.10.2015