素数をまとめてふるいにかける

1個ずつ割り算を繰り返す代わりに、素数の倍数をまとめて消します。上限までの素数を列挙するときに使います。

言語：Python / 計算量：O(N log log N)、メモリ O(N)

前提：最大公約数とユークリッドの互除法

考え方

1. 0と1は素数ではありません。
2. 残った数pを素数として、p²から倍数を消します。
3. p²より小さい合成数は小さい素因数で既に消えています。

具体例

10以下では2の倍数4,6,8,10、3の倍数9を消すと2,3,5,7が残ります。

実装

n=10
isprime=[True]*(n+1);isprime[0]=isprime[1]=False
p=2
while p*p<=n:
    if isprime[p]:
        for x in range(p*p,n+1,p):isprime[x]=False
    p+=1
print([i for i in range(n+1) if isprime[i]])

注意する条件

10^12までの配列を作ることはできません。上限が大きい1個の整数を判定する課題とは別です。

確認問題

10以下の素数の個数は？

実装課題

N（2≤N≤10^6）以下の素数の個数を出す。

入力:
10
出力:
4

n=int(input());p=[True]*(n+1);p[0]=p[1]=False
i=2
while i*i<=n:
    if p[i]:
        for j in range(i*i,n+1,i):p[j]=False
    i+=1
print(sum(p))

読了の記録・下書き・メモへ