Обновление списка/набора для повтора в цикле for

Question

Я пытаюсь создать набор простых чисел, используя метод Сита. Но похоже, что prime = prime - set(range(2*n,N,n)) не обновляет набор prime в for n in prime:.

N = int(raw_input()) + 1 
prime = set(range(2,N)) 

for n in prime: 
    print n 
    prime = prime - set(range(2*n,N,n)) 

Например, ввод N = 100. Выходной сигнал 1,2,3,...,100, что делает код очень медленным. Что делать, чтобы обновлять набор последовательно?

Edit: Немного глубже: Можете ли вы объяснить разницу между усиленными и не усиленными заданиями? Неужели я не могу добиться всего одного набора? Поскольку это просто кажется наивным, и я не могу поверить в такой язык высокого уровня, поскольку Python этого не может достичь, поскольку в C++ я могу сделать это с помощью всего лишь массива логических значений.

Answer 1

Цикл for оценивает итерируемое выражение просто один раз. Вы не изменяя prime, вы перекомпоновка имя для нового объекта (выход prime - set(range(2*n,N,n)), петля for никогда не будет видеть.

Заметим также, что for перебираем set будет делать это в произвольном порядке ; цифры не сортируют вы могли легко быть переданы не-премьером первого

Если вы использовали дополненное задание, чтобы изменить prime в месте, однако, вы получите сообщение об ошибке, о изменении заданного времени.. итерационные:

>>> N = 50 
>>> prime = set(range(2, N)) 
>>> for n in prime: 
...  print n 
...  prime -= set(range(2 * n, N, n)) 
... 
2 
Traceback (most recent call last): 
    File "<stdin>", line 1, in <module> 
RuntimeError: Set changed size during iteration 

Вы должны петли непосредственно над range() и отслеживать, не являющиеся простыми числами вместо:

non_prime = set() 
primes = [] 

for n in range(2, N): 
    if n in non_prime: 
     continue 
    non_prime |= set(range(2 * n, N, n)) 
    primes.append(n) 

Демо:

>>> non_prime = set() 
>>> primes = [] 
>>> for n in range(2, N): 
...  if n in non_prime: 
...   continue 
...  non_prime |= set(range(2 * n, N, n)) 
...  primes.append(n) 
... 
>>> primes 
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47] 

или вы могли бы использовать while цикл с кандидатами установить вы пустой :

candidates = set(range(2, N)) 
primes = [] 

while candidates: 
    n = min(candidates) 
    candidates -= set(range(2 * n, N, n)) 
    candidates.remove(n) 
    primes.append(n) 

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

Обратите внимание, что здесь вы можете уменьшить диапазон размеров, используя range(n * n, N, n); все 2 * n ценности прошлых 2 * 2 бы уже были ликвидированы, все 3 * n мимо 3 * 3, а также, и т.д .:

>>> primes = [] 
>>> for n in range(2, N): 
...  if n in non_prime: 
...   continue 
...  non_prime |= set(range(n * n, N, n)) 
...  primes.append(n) 
... 
>>> primes 
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47] 

Последнее, но не менее, общий способ реализации сито, чтобы использовать список булевы, чтобы выделить не являющиеся простые числа:

sieve = [True] * N 
sieve[0] = sieve[1] = False 
primes = [] 

for (n, is_prime) in enumerate(sieve): 
    if is_prime: 
     primes.append(n) 
     for n in range(n * n, N, n): 
      sieve[n] = False