Page:Shinshiki Sanjutsu Kogi 00.djvu/149

133

（六）

エラトステネスの篩

---

整數の中より素數を撰み出す方法は既に古希臘の數學者の知れる所にして，所謂エラトステネスの篩是なり．

${\begin{array}{rrrrrrrrrr}&2&3&{\underline {4}}&5&{\underline {6}}&7&{\underline {8}}&{\underline {9}}&{\underline {10}}\\11&{\underline {12}}&13&{\underline {14}}&{\underline {15}}&{\underline {16}}&17&{\underline {18}}&19&{\underline {20}}\end{array}}$

整數を自然の順序に書き列べ先づ $1$ を去るとき，最初に殘れる數 $2$ は素數なり．何とならば $2$ に眞の約數あらば，そは $2$ より小なる整數にして，$2$ より小なる整數は $1$ を外にして之なければなり．さて $2$ より二つ目每の數 $4,6,8,10\ldots$ に符標を附すべし．$2$ の次に符標を帶ばざる數は $3$ にして，$3$ は素數なり，何とならば $3$ に眞の約數あらば，そは $2$ ならざるを得ず，然れども $3$ に符標なきは其 $2$ の倍數に非ざるを示せばなり．さて $3$ より三つ目每の數に符標を附し，殘れる最初の數 $5$ の素數なるを知り，$5$ より五つ目每の數に符標を附し，斯の如く進みて遂に $p$ なる素數に達したりとせよ．さて此時 $p^{\pi }$ 以下の數にして未だ符標を帶ばざるものは盡く素數なり．例へば $a$ を符標なき數