素数判定の試し割り法エラトステネスの篩とは

どうも、木村（@kimu3_slime）です。

今回は、素数かどうかの判定法として、エラトステネスの篩を紹介します。

エラトステネスの篩とは
素数の判定法
こちらもおすすめ

エラトステネスの篩とは

素数とは、1とそれ自身以外に約数を持たない数のことでした。素数ではない数を合成数と呼びます。

つまり、\(2\)で割り切れる\(2\)以外の数は素数ではありませんし、\(3\)で割り切れる\(3\)以外の数は素数ではありません。小さな数で割りきれる数（合成数）をはじいていくことで素数を見つける方法は、エラトステネスの篩（ふるい）（sieve of Eratosthenes）として知られるものです。（エラトステネスは、古代ギリシャの数学者です）

\(50\)以下の整数について、エラトステネスの篩にかけてみましょう。まず、数を並べて、2で割り切れる数を消していきます。

さらに、3の倍数を消します。素数でない数、合成数をふるいおとしているようすがわかりますね。

5の倍数を消します。かなり減ってきました。

7の倍数を消します。

割る数となった最初の数\(2,3,5,7\)は素数です。そして、残った数\(11,13,17,19\),\(23,29,31,37\),\(41,43,47\)が素数の候補になります。実は、候補であるだけでなく、実際にこの方法では、\(7^2=49\)以下の素数が見つけられるのです。

素数の判定法

与えられた整数\(x\)が素数かどうかは、「ある程度小さな」素数すべてによって割り切れるかどうかで判定できます。

\(x\)を2以上の整数とする。\(\sqrt{x}\)以下のすべての素数\(p\)（\(p \leq \sqrt{x}\)）で割り切れないなら、\(x\)は素数である。

対偶を示しましょう。\(x\)が合成数ならば、\(x\)は\(p \leq \sqrt{x}\)を満たすある素数\(p\)で割り切れることを示します。

\(x\)を合成数（素数でない）と仮定します。\(1\)でも\(x\)でもない約数を持つので、\(x=ab\)、\(2\leq a <x\)、\(2\leq b <x\)を満たす整数\(a,b\)が存在します。\(a\)は2以上の整数なので、素因数分解したときに少なくともひとつの素数を含みます。つまり、\(a=p_1 p_2 \cdots p_N\)と表せます（算術の基本定理）。\(p=p_1\)と置きましょう。\(p\)は素数であり、\(a\)を割り切り\(p \mid a\)、したがって\(p\)は\(x\)も割り切ります。また、\(p \leq p_1 p_2 \cdots p_N= a \leq \sqrt{x}\)が成り立ちます。なぜなら、\(a\leq b\)のとき、\(a^2 \leq ab =x\)でルートを取れば良いからです（\(a\geq b\)でも、\(b\)を素因数分解して同様に議論できる）。よって、\(x\)を割り切る素数\(p\)で、\(p \leq \sqrt{x}\)を満たすものが存在することが示せました。

この判定法は、エラトステネスの篩の原理です。\(10=\sqrt{100}\)以下の素数は、\(2,3,5,7\)と知っているとしましょう。そして、数\(x\)を\(2,3,5,7\)で割ってみて、割り切れない数を考えます。その数は、さきほど示したことにより素数であると言えるわけです。図としては\(50\)までしか書きませんでしたが、\(7\)で割り切れるかチェックした時点で、\(100\)以下の素数を見つけられます。

\(x\)が素数かどうか判定するために、\(x\)以下のすべての素数で割りきれるかどうか試さなくても、\(\sqrt{x}\)以下の素数を調べれば良い、というわけです。

\(151\)が素数かどうか判定してみましょう。\(12 \leq \sqrt{151} < 13\)なので、\(11\)までの素数で割り切れるか調べれば十分です。\(2,3,5\)で割り切れないのは良いでしょう。\(140+11\)なので\(7\)で割り切れません。\(110+41\)なので\(11\)でも割り切れません。よって、\(151\)は素数です。

ルートの不等式について：ルートの近似値の求め方不等式を使って大小比較

\(2021\)が素数であるかどうか判定してみましょう。\(40 \leq \sqrt{2021} \leq 50\)なので、\(50\)以下の素数で割り切れるか調べれば十分です。ちょっと多いですが、上で得た\(50\)以下の素数の表を使って、地道にやってみましょう。

\(2\)では割り切れません。\(1800+221\)なので、\(3\)で割り切れません。\(2100-79\)なので、\(7\)で割り切れません。\(2200-179\)なので、\(11\)で割り切れません。\(1300+650+71\)なので、\(13\)で割り切れません。\(1700+340-19\)なので、\(17\)で割り切れません。\(1900+95+26\)なので、\(19\)で割り切れません。\(2300-230-49\)なので、\(23\)で割り切れません。\(29*70-9\)なので、\(29\)で割り切れません。\(1860+161\)なので、\(31\)で割り切れません。\(2220-99\)なので、\(37\)で割り切れません。\(2050-29\)なので、\(41\)で割り切れません。

……ところが、\(43 \cdot 47=2021\)と割り切れてしまいます。つまり、\(2021\)は素数でないことがわかりました。

より大きな数になると、手計算ではかなりしんどくなりそうですね。コンピュータで計算するにしても、素数判定には工夫が必要となってくることがわかります。

以上、素数かどうかの判定法として、エラトステネスの篩を紹介してきました。

3桁や4桁くらいまでの数なら、この方法で手計算してチェックできるので、町中で出会った数に対して素数かどうか判定してみてください。

木村すらいむ（@kimu3_slime）でした。ではでは。