Python Сито Эратосфена не работает

Question

Прежде всего, это HOMEWORK, в настоящее время я работаю над ситом Эратосфена на python. Моя программа выглядит так:

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)

Когда моя программа печатает для "простых чисел", я получаю:

[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]

Почему в списке есть составные числа? Похоже, программа должна работать

#

Отредактировал программу, теперь она выглядит так:

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='')

Все еще не работает, получаю ошибку; "ValueError: list.remove(x): x отсутствует в списке"

Answer 1

Одна проблема - ты только добавляешь i, Вам нужно сбросить i вернуться к 2 каждый раз, когда вы выталкиваете другой элемент из списка.

То есть сначала вы поп 2 из списка. Вы постепенно увеличиваете i удалить все кратные 2 из списка. В конце этого, i будет 50. Но затем вы вернетесь и выскочите 3 из списка, и i еще 50, так что он ищет только 50*3 в списке.

Даже если вы исправите это, оно все равно не будет работать, потому что вы перестанете смотреть на i значения, как только вы найдете тот, которого нет в списке. Но возможно, что k*i не в списке, но k*(i+1) это - например, после того, как вы наберете кратные 2, первое кратное 3 (а именно 6) не будет в списке, а следующее (а именно 9) есть. Таким образом, вы не можете остановиться, пока не попробуете все кратные до макс.

Answer 2

Вы должны принять ответ @BrenBarn, поскольку он охватывает важные вещи. Но вот еще несколько советов:

• Существует более простой и быстрый способ сделать начальный x список.

Пусть Python сделает это за вас. Просто заверните range() в list() вот так:

MAX_NUM = 100
x = list(range(2, MAX_NUM))

У нас будет больше возможностей для использования MAX_NUM потом; читать дальше.

• В Python лучше всего использовать for цикл с range() вместо while Добавление цикла в индексную переменную.

Вместо:

i = 2
while k*i <= max(x):
    # do stuff with k*i
    i += 1

попробуй это:

for i in range(k*2, max(x), k):
    # do stuff with i

Python встроенный range() сделает ряд значений для вас, начиная с k*2, добавив k каждый раз и останавливаясь с последним кратным k это меньше чем max(x), Теперь ваш цикл работает быстрее, и вы избегаете многократного умножения.

• Вместо индексации x[0] получить k а затем с помощью x.pop() отказаться от k значение от xЕсть более простой способ.

list.pop() возвращает всплывающее значение. Таким образом, вы можете сделать это в одну строку следующим образом:

k = x.pop()

• Вы вычисляете max(x) много раз. Но вы уже знаете, наибольшее число в xпотому что ты построил x, В то время, когда вы строите xВы можете сохранить наибольшее число в переменной и использовать эту переменную вместо поиска max(x) вновь и вновь. Хорошая часть о max(x) является то, что он не будет проверять номера, которые были извлечены; например, когда k 3, 99 будут удалены. Но max(x) это дорого, поэтому я считаю, что использование сохраненного значения - это в целом выигрыш.

Вот почему я спас MAX_NUM, Так что вы можете сделать это:

for i in range(k*2, MAX_NUM, k):
    # do stuff with i

• Если вы только начинаете, вы можете не знать о Python set() класс, но это хорошо для этой проблемы. Как сказал Дстромберг в своем ответе, x.remove(some_value) медленно когда x содержит много значений. Но удаление значений из set всегда очень быстрая операция.

Вы можете построить набор следующим образом:

x = set(range(2, 100))

Этот набор будет содержать все целочисленные значения от 2 до 99 включительно.

Затем одна из приятных вещей о наборах: вы можете избавиться от членов, не проверяя, есть ли они в наборе, с помощью .discard() функция-член (еще одна дешевая вещь, чтобы сделать с set).

# list solution
if i in my_list:
    my_list.remove(i)

# set solution
my_set.discard(i)

На самом деле, оба in (используется в списке) и list.remove() дорогие Так что set заменяет две дорогостоящие операции на одну дешевую!

Как только вы переведете исходную программу в рабочее состояние, сохраните ее копию, а затем перепишите ее, чтобы использовать set вместо list, Увеличьте наибольшее целое число от 100 до, скажем, 10000 и время обеих программ. Вы должны заметить разницу. set займет больше времени, чем сделать list но тогда вы выиграете большой выигрыш на операциях (in тесты или удаление значения).

• Но вы можете быть удивлены, "Steveha, а set не может быть проиндексирован так x[0] не сработает... как мне найти k?"

Я предлагаю просто использовать for петля с range() утверждение, которое делает k ценности, которые вам нужны. Вместо того чтобы смотреть на x[0] или используя k = x.pop(), вы можете сделать это:

for k in range(2, MAX_NUM):
    if k not in x:
        continue

С set in Тест очень быстрый, поэтому он быстро пропускает все не простые числа. Это не так умно, как в оригинальной программе всегда есть следующий готовый вариант, но в целом я думаю, что set это победа для этой проблемы.

И, эй, мы смогли использовать MAX_NUM в другой раз.

• Вы также можете думать "А set не имеет .pop() так, как я могу получить свой список простых чисел, когда сито закончено? "

Не может быть проще!

result = list(my_set)  # get a list of values stored in my_set

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

• Возможно, вы захотите использовать несколько лучшие имена переменных. Лично мне нравятся краткие однобуквенные переменные, если они используются в компактном коде, который остается вместе, поэтому я хотел бы сохранить i, но возможно x должно быть sieve а также k должно быть next_prime или что-то.

• Я рад видеть, что вы понимаете, как использовать более продвинутые функции print() функция, но я думаю, что ваш код печати может быть проще.

Вместо этого:

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

Попробуй это:

print('primes')
print(primes)

Или, может быть, это:

print('primes:\n{}'.format(primes))

Фактическая программа, в которой используются все вышеприведенные советы для вычисления сита Эратосфена, намного короче, чем был совет! Я написал и протестировал его, но я не буду публиковать его, если вы не захотите, чтобы я это сделал. Мое решение (не считая print() звонки или пустые строки) - это 8 строк Python, а первая строка: MAX_NUM = 100 (РЕДАКТИРОВАТЬ: это было шесть строк, но у меня не было чека, чтобы увидеть, k есть в наборе или нет, поэтому было медленно. Проверка добавила еще две строки.)

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

Одна из вещей, которые мне нравятся в Python - это то, что когда программа эффективно использует встроенные функции Python, она становится более простой и красивой программой, которую легче понять.

Удачи и приятного времяпровождения!

Answer 3

Комментарии:

• Следует использовать более описательные имена переменных
• Нужно перезапустить i на 2 каждый раз, вводя k * i в цикле x
• x.pop(0) медленно для больших x
• x.remove (k * i) медленно для больших x
• Следует изменить внутренний цикл while на "while k * i

Вот работающее и быстрое сито, которое использует список битов: http://stromberg.dnsalias.org/svn/sieve/trunk/