エラトステネスのふるい
https://upload.wikimedia.org/wikipedia/commons/6/63/Animation_Sieb_des_Eratosthenes.gif
code:py
def sieve(n):
for i in range(2, n):
if i not in primes:
continue
for j in range(i * 2, n, i):
if j in primes:
primes.remove(j)
return primes
code:py
def sieve(n):
for i in range(2, n):
continue
for j in range(i * 2, n, i):
return primes
高速化
奇数を対象にする(2は特別扱い)
など
ref