エラトステネスの篩
SPF
を計算する。
code: sieve.py
def sieve(N):
"""
エラトステネスの篩 O(NloglogN)
"""
table =
0 for _ in range(N+1)
# SPF
for i in range(2, N+1):
if table
i
: continue
j = i
while j <= N:
if not table
j
:
table
j
= i
j += i
prime = [i for i in range(2, N+1) if table
i
== i]
return prime