Разбор работы самой быстрой из известных мне реализаций решета Эратосфена на Vanilla Python, т.е. без использования дополнительных модулей.
(c) Bruno Astrolino E Silva - я лишь добавил отладочную информацию:
def primes(n, verbose=0):
""" Returns a list of primes < n """
# (c) Robert William Hanks - https://stackoverflow.com/a/3035188/5741205
def pr(*args):
if verbose > 0:
print(*args)
sieve = [True] * n
pr("все чётные числа игнорируются и будут пропущены при возврате...\n")
for i in range(3,int(n**0.5)+1,2):
if sieve[i]:
pr('содержимое решета:\t{}'.format([x for x in range(3,n,2) if sieve[x]]))
pr(f'i:{i} вычёркиваем все числа кратные "{i}", начиная с "{i}^2": {list(range(i*i, n, 2*i))}')
sieve[i*i::2*i]=[False]*((n-i*i-1)//(2*i)+1)
pr(f'sieve[{i}*{i}::2*{i}]=[False]*(({n-i}*{i-1})//(2*{i})+1)')
pr('содержимое решета:\t{}'.format([x for x in range(3,n,2) if sieve[x]]))
pr('*' * 60)
return [2] + [i for i in range(3,n,2) if sieve[i]]
PS данная реализация очень эффетивно использует срезы и, благодаря этому, минимизирует число итераций цикла - в примере ниже для нахождения всех простых чисел меньше 50
, понадобилось всего три итерации цикла.
Вывод для n=50
:
In [165]: primes(50, verbose=1)
все чётные числа игнорируются и будут пропущены при возврате...
содержимое решета: [3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49]
i:3 вычёркиваем все числа кратные "3", начиная с "3^2": [9, 15, 21, 27, 33, 39, 45]
sieve[3*3::2*3]=[False]*((47*2)//(2*3)+1)
содержимое решета: [3, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49]
************************************************************
содержимое решета: [3, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49]
i:5 вычёркиваем все числа кратные "5", начиная с "5^2": [25, 35, 45]
sieve[5*5::2*5]=[False]*((45*4)//(2*5)+1)
содержимое решета: [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49]
************************************************************
содержимое решета: [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49]
i:7 вычёркиваем все числа кратные "7", начиная с "7^2": [49]
sieve[7*7::2*7]=[False]*((43*6)//(2*7)+1)
содержимое решета: [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
************************************************************
Out[165]: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47