Построчная разбивка:
def primes(n):
if n==2: return [2]
Эта функция возвращает список простых чисел <= n. Так что если n == 2, этот список содержит только 2. Достаточно просто.
elif n<2: return []
Здесь снова нет простых чисел ниже 2, поэтому верните пустой список.
s=range(3,n+1,2)
Итак, s - это список нечетных чисел, начиная с 3 и заканчивая n + 1. s обозначает сито - это алгоритм сита, который означает, что составные (не простые) числа будут исключены из списка. По сути, они будут «перечеркнуты». Ниже приведено подробное описание алгоритмов сита.
mroot = n ** 0.5
Поскольку это сито, мы можем остановить алгоритм, как только достигнем квадратного корня из n.
half=(n+1)/2-1
Это явная формула для длины s; его можно заменить на len(s), но это может занять больше времени для расчета при больших значениях n. Это также будет полезно для завершения определенных частей алгоритма.
i=0
m=3
Я - наш индекс; Я просто перешагиваю через сито, проверяя каждое значение. Если значение 0, то число было «вычеркнуто», потому что оно не простое. m - это просто значение s[i] в любой данный момент; более поздняя строка держит это обновленным.
while m <= mroot:
if s[i]:
Поскольку s[i] оценивается как True, он еще не вычеркнут из списка. Это означает, что это главное! Итак, теперь мы должны выяснить, какие числа в списке кратны s[i] - все они не простые числа и должны быть вычеркнуты из списка.
j=(m*m-3)/2
s[j]=0
Теперь начинается самое интересное. Поскольку сито - это не список последовательных чисел, а список нечетных чисел, мы должны выяснить, где кратные нашего простого числа живут в s. В этом случае наше простое число равно 3, поэтому нам нужно найти индекс 9, 15, 21, 27 ... (нам не нужно находить 6, 12, 18 ... потому что они даже и так нет в списке). Эта конкретная техника для нахождения индексов действительно умна, потому что автор понял, что после того, как все кратные определенного простого числа были вычеркнуты, они могут быть пропущены. Это означает, что первое не вычеркнутое кратное нашего простого числа на самом деле является квадратом этого простого числа. (Так, например, если бы простое число было 7, 7 * 3 = 21 и 7 * 5 = 35 уже было бы вычеркнуто, поэтому первое кратное число 7, с которым мы должны иметь дело, это 7 * 7.) Как только это делает в смысле, довольно легко увидеть, что расположение 9 в s равно (9 - 3) // 2 (где // - деление по полу).
while j<half:
s[j]=0
j+=m
Теперь все возвращается к простоте. Мы нашли 9; теперь мы должны найти 15 = 9 + 3 + 3. Поскольку s содержит только нечетные числа, это вдвое меньше, чем список с каждым числом; чтобы пропустить 6, нам нужно только добавить 3 к j. Мы делаем это, пока j меньше half - другими словами, пока j меньше длины s.
i=i+1
m=2*i+3
Опять же, просто - i - это просто индекс списка, а m - это значение числа, которое было там изначально. (Вы можете проверить это, чтобы понять, почему: [2 * i + 3 for i in range(10)].)
return [2]+[x for x in s if x]
И вуаля - отфильтруйте нули из сита, добавьте [2] и у вас есть список простых чисел.
Наиболее запутанная вещь в этом алгоритме связана с ярлыками, выбранными автором, которые ускоряют его выполнение, но затуманивают фундаментальную концепцию. (На самом деле, есть еще несколько ярлыков, которые можно использовать, но это другой пост.) Вот гораздо более простое сито, которое показывает основную идею:
>>> numbers = range(40)
>>> numbers[1] = 0 # 1 isn't prime
>>> for i in numbers:
... if i:
... for j in range(i + i, len(numbers), i):
... numbers[j] = 0
...
>>> [n for n in numbers if n]
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
Чтобы разобраться, первые числа выглядят так:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10...]
Тогда ...
[0, 0, 2, 3, 4, 5, 6, 7, 8, 9, 10...]
[0, 0, 2, 3, 0, 5, 0, 7, 0, 9, 0...]
[0, 0, 2, 3, 0, 5, 0, 7, 0, 0, 0...]
И так далее.