Как использовать понимание списка в алгоритме «Решето Аткина»? [закрыто] ⇐ Python

[Anonymous]

Я пишу программу на Python для поиска списка простых чисел.
Я написал ее, используя решето Эратосфена:

Код: Выделить всё

def Eratosthenes(n:int) -> list[int]:
if n  n:
break
for j in range(i//2-1+i,n//2-1,i):
l[j] = 0
return [2]+[i for i in l if i]

Потом я услышал, что Решето Аткина намного быстрее, поэтому я написал и эту версию:

Код: Выделить всё

import math

def Atkin(n:int) -> set[int]:
s1 = {1,13,17,29,37,41,49,53}
s2 = {7,19,31,43}
s3 = {11,23,47,59}
sq = {i*i for i in range(1,math.isqrt(n)+1)}
l = [2,3,5]
for x in sq:
for y in sq:
txpy = 3*x+y
fxpy = txpy+x
txmy = txpy-2*y
if txpy < n and txpy%60 in s2:
l.append(txpy)
if fxpy < n and fxpy%60 in s1:
l.append(fxpy)
if txmy < n and txmy>0 and txmy%60 in s3:
l.append(txmy)
for i in l:
if i == 0:
continue
for k,v in enumerate(l):
if v  0}

Но я понял, что сделал ужасный код, потому что эта версия даже медленнее той, которая использует Решето Эратосфена. Я думаю, что одной из причин может быть то, что я использовал + добавление вместо понимания списка. Как я могу улучшить этот код?
Я только что обнаружил, что есть еще одна проблема: алгоритм «Решето Аткина» не исключает 91 и множество других составных чисел. Теперь я исправил алгоритм.
Моя реализация была основана на этом видео на YouTube с 3:14 по 4:40. Это не сработало.

Подробнее здесь: https://stackoverflow.com/questions/792 ... -algorithm