Here is a very effective implementation of the Eratosthenes sieve (c) Robert William Hanks - I just added debug information:
def primes(n): """ Returns a list of primes < n """ # (c) Robert William Hanks - https://stackoverflow.com/a/3035188/5741205 sieve = [True] * n print("все чётные числа игнорируются и будут пропущены при возврате...\n") for i in range(3,int(n**0.5)+1,2): if sieve[i]: print('содержимое решета:\t{}'.format([x for x in range(3,n,2) if sieve[x]])) print(f'i:{i} вычёркиваем все числа кратные "{i}", начиная с "{i}^2": {list(range(i*i, n, 2*i))}') sieve[i*i::2*i]=[False]*((ni*i-1)//(2*i)+1) print(f'sieve[{i}*{i}::2*{i}]=[False]*(({ni}*{i-1})//(2*{i})+1)') print('содержимое решета:\t{}'.format([x for x in range(3,n,2) if sieve[x]])) print('*' * 60) return [2] + [i for i in range(3,n,2) if sieve[i]]
Output for n=50
:
In [165]: primes(50) все чётные числа игнорируются и будут пропущены при возврате... содержимое решета: [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
n
is the limit. In your case,n = 2*10**6
. - Mikhail Murugov