Неспособность понять синтаксис простого сита

Question

Может ли кто-нибудь пройти меня по линии этого сима? Я пытаюсь разработать собственное сито, но большинство более быстрых содержат синтаксис, который я не понимаю (например, строки, на которых я комментировал). Извините, если это своего рода вопрос новичков - также если у вас есть какие-либо ссылки, которые могли бы помочь мне с ситовым письмом, они были бы весьма признательны.

def rwh_primes1(n): 
    """ Returns a list of primes < n """ 
    sieve = [True] * (n/2) # What does the '[True]' mean? 
    for i in xrange(3,int(n**0.5)+1,2): 
     if sieve[i/2]: # The same complaint as in line 3, I don't understand the variable 'sieve' 
      sieve[i*i/2::i] = [False] * ((n-i*i-1)/(2*i)+1) # how is sieve used here - it seems to be as a list but i'm unsure 
    return [2] + [2*i+1 for i in xrange(1,n/2) if sieve[i]] # 'sieve' is confusing me here yet again. 

Answer 1

Я расскажу о значении каждой строки кода курсивом и добавлю свои комментарии в текст обычного текста.

sieve = [True] * (n/2) 

Объявите новую локальную переменную sieve и инициализирует его значением [True] * (n/2). Что означает это выражение? [True] - это одноэлементный список, содержащий только логическое значение True. Умножение списка на число повторяет список, поэтому sieve теперь является n/2 -элементным списком всех значений True.

for i in xrange(3, int(n**0.5)+1, 2): 

начать отсчет с шагом 2, начиная с 3 и заканчивающийся в SQRT (п). Этот конкретный выбор диапазона - это оптимизация алгоритма сита: мы могли рассчитывать все от 1 до n с шагом 1, но это было бы менее эффективно.

if sieve[i/2]: 

Посмотрите на i/2-й элемент sieve списка. Если это True, продолжайте движение вниз по ветке if. Автор использует i/2, чтобы компенсировать тот факт, что код подсчитывается с шагом 2. Таким образом, вы можете работать с более коротким списком и использовать меньше памяти.

sieve[i*i/2::i] = [False] * ((n-i*i-1)/(2*i)+1) 

Обновление каждый I-й элемент sieve к False, начиная с я * I/2.sieve[i*i/2::i] называется slice notation - потому что он появляется в левой части задания, этот код будет обновить, что кусок sieve. Правая часть - это повторение трюка с номером списка. Он вычисляет список правильной длины для всего False.

return [2] + [2*i+1 for i in xrange(1,n/2) if sieve[i]] 

Этот код просто превращает значения в True/False в sieve в список простых чисел. Расчет компенсации за то, что sieve не содержит каких-либо четные числа от умножения индекса каждого True значение, на 2.

Answer 2

Пусть п = 7:

sieve = [True] * (n/2) # What does the '[True]' mean? 

Составьте список логических Истинные значения длины половина n. Например, сито = [Правда, True, True] (как 3.5 был длиной фракции она округляется вниз в python2)

Так xrange(3,int(n**0.5)+1,2) будет генератор, который дает нам эту последовательность: []

for i in 
     if sieve[i/2]: # The same complaint as in line 3, I don't understand the variable 'sieve' 
      sieve[i*i/2::i] = [False] * ((n-i*i-1)/(2*i)+1) # how is sieve used here - it seems to be as a list but i'm unsure 
    return [2] + [2*i+1 for i in xrange(1,n/2) if sieve[i]] # 'sieve' is confusing me here yet again. 

Когда мы видим [i :: 2], или что-то вроде того, что мы просто срезаем список с повторяющимися интервалами. Поэтому, если mylist содержит (0 ..19):

>>> mylist = range(20) 
>>> mylist[0::1] 
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] 
>>> mylist[0::2] 
[0, 2, 4, 6, 8, 10, 12, 14, 16, 18] 
>>> mylist[0::3] 
[0, 3, 6, 9, 12, 15, 18] 

Попробуйте сыграть с этим сами, чтобы вы были знакомы с ним. Итак, в этом случае sieve[i*i/2::i] = [False] * ((n-i*i-1)/(2*i)+1) будет устанавливать для каждого i-го значения в списке значение False.