はじめに
Atcoder Biginner Contest170にて、エラトステネスの篩の考え方を応用させるというのを見て、エラトステネスの篩すらまともに理解できてないままではいかんと思い執筆を決意しました。
実用性というよりは原理の理解のための記事なのでコンテスト中などにたどり着いた方はこちら
がおすすめです。(いつも参考にさせていただいているいかたこのたこつぼさんのHPです)
素数判定
試し割り法
まずは、試し割り法と呼ばれる手法を用います。2よりも大きい数で順に割っていき、割り切れたらその数を約数に持つということなので素数ではありません。
しかし、$N$まで全ての数で割っていく必要はありません。$N$が約数$d$を持つとすると、$N/d$も$N$の約数であり、どちらか小さい方で割れば十分です。小さい方が最大となるのは、これら2つが等しくなるときなので、(小さい方が大きい方を抜かすとそれはもう調べ終わっている) $\sqrt{N}$まで調べれば十分ということになります。
以上より、この素数判定は$O(\sqrt{N})$で計算可能です。
ここで、高速化のポイントとして、偶数を約数に持つなら2で割り切れているはずなので、2以降は奇数のみを調べると良いそうです。(今回は考慮しません)
# O(√N)
def is_prime(n):
if n == 1:
return True
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
return False
return True
エラトステネスの篩
次に、エラトステネスの篩という手法を見ていきます。これは、$N$以下の素数を全列挙してしまうという考えで、判定する対象が複数の場合は前処理さえしてしまえばあとは$O(1)$で判定可能になります。デメリットとしては、大きさ$N$の配列が必要となるので使用メモリがそれなりに大きくなります。
ではどのように素数テーブルを作成するかを見ていきます。まず、すべての数を素数の候補と考えます。1は素数でないので候補から消しておきます。(配列の都合上、0も含んでしまっていますが素数ではないので消しておくという実装になっています)
次に、2から順に小さい方から数を見て、もしその数が素数ならばその倍数は合成数となります。よって、倍数全てを候補から消していきます。このように篩にかけて候補から落としていくように見えるからエラトステネスの篩と呼ばれるっぽいです。
計算量は、少し複雑ですが一応得た知見を垂れ流しておきます。各素数で割ることのできる回数は素数をpとすると$N/p$回で、最初だけ書くと
$$N(1/2 + 1/3 + 1/7 + ...)$$
となります。ここで、$N$までの素数の逆数和は十分大きい$N$に対して$loglogN$くらいらしい(詳しくはgoogle)ので、計算量は$O(NloglogN)$です。まあかなり$O(N)$に近そうだなと思います。
これにも高速化のコツがあり、最初のループを$\sqrt{N}$までしか回さないとか2以降の偶数は省くとかいろいろありそうなので是非調べてください!(もちろん今回は反映していません)
# O(NloglogN)
def eratosthenes_sieve(n):
is_prime = [True]*(n + 1)
is_prime[0] = is_prime[1] = False
for p in range(2, n + 1):
if is_prime[p]:
for q in range(2*p, n + 1, p):
is_prime[q] = False
return is_prime
返すのは素数テーブルなので、一応使い方も書いておきます。
n = 10
is_prime = eratosthenes_sieve(n)
print(is_prime[5]) # True
print(is_prime[10]) # False