エラトステネスの篩

今回はエラトステネスの篩についてやっていきます。命題4を示し、本題であるエラトステネスの篩とは何なのかまで軽くまとめていきたいと思います。

エラトステネスの篩

前回の記事にも公理としてまとめているのですが、ここでも一応、書いておきます。

エラトステネスの篩を考える上で必要となる命題4を示すための準備をここからしていきます。

証明
$b|a$より$a = bn$となる$n \in \mathbb{Z}$がある。
$a \ne 0$より、$n \ne 0$である。$|n| > 0$は整数なので、公理より$|n| \geqq 1$.
よって、$|a| = |b||n| \geqq |b|$ □

この命題の証明は簡単のため、省略します。

証明
$n$が素数でなければ、$1 < m < n$を$n$の約数とする。
$1 < m < n$で、$m$の約数で素数であるものが存在するとする。
$m$に関する帰納法を使うと、$m$の約数である素数$p$が存在する。
命題2(1)より、$p$は$n$の約数である。□

証明
もし、$n$が合成数なら、$1,n$以外の正の約数$l$を持つ。
$m = n/l$とおくと、$l,m \ne 1,n \hspace{2mm},\hspace{2mm} n = lm$である。
もし、$l,m > \sqrt{n}$なら、$lm > n$となり矛盾する。
よって、$n$は$\sqrt{n}$以下の約数を持つ。

$l | n \hspace{2mm},\hspace{2mm} l \leqq \sqrt{n}$とする。
$l | n$で、$n$は合成数なので、$1 < l < n$である。
命題3より、$l$の約数で素数であるものがある。その素数を$p$とおく。(当然、$p | l$である。)
命題1より、$p,l$は正の整数で、$l \leqq \sqrt{n}$なので、$p \leqq l \leqq \sqrt{n}$.

以上で、命題4が示された。□

ここまでの命題4つ(特に命題4)を使って、エラトステネスの篩について説明していきます。

命題4の結果から、$N_1$以下の素数がすべて分かれば、$N_2 = N_1^2$までの数でそれらの素数の倍数である合成数を除けば、$N_2$までの素数がすべてわかります。これを繰り返していくと、どんな数でも素数であるかどうかを判定することが可能になります。この方法をエラトステネスの篩ふるいといいます。具体例を一つ見てみましょう。

命題4から、合成数$n$は$\sqrt{n}$以下の約数を持つので、$n \leqq 100$なら、$\sqrt{n} \leqq \sqrt{100} = 10$.
つまり、100以下の合成数は2 , 3 , 5 , 7のどれかで割り切ることができる。

これを踏まえて、100以下の整数のなかで素数がどれだけ含まれているのかを見ていくと、

1から100までの素数

この方法は、$n$が素数であるかどうかを判定するのに、$\sqrt{n}$以下の素数を調べれば十分であることが分かります。なぜなら、$n$が合成数であったとすると、$\sqrt{n}$以下の素数の約数を持つからです。

今回は以上です。