1. 素数ってなーに？
私たちの身の回りにはいろいろな数字があります。身長が173センチ。体重は62.5Kgなどなど。
数字を数学的に分けると
自然数 １、２、３、４、5・・・・・
1から始まり、1ずつ増加する数
整数 -5、-4、-3、-2、-1、0、1、2、3、4、5
原点を0として＋、ー方向に1づつ変化する数。
そのほかに有理数、無理数などありますが、これから扱う素数は自然数なので、またの機会に取り上げましょう。
素数とは、１と自分自身しか約数を持たない（１と自分自身でしか割り切れない）自然数です。例えば11の約数は１と11しかありません。なので11は素数になります。16を調べてみましょう。16の約数は１、２、４、8、16です。約数に１と自分自身以外の数字（２、4、8）が入っているので16は素数ではありません。16のように、約数の中に1と自分自身以外の数字があるものを合成数といいます。
2. 総当たりで素数を見つけよう
最も愚直な方法ですが、やってみましょう。
１は素数ではありません。そのあたりは改めて扱いましょう。
２の約数は（１、2）なので、２は素数です。
３の約数は（１、3）なので、３は素数です。
４の約数は（1、２、4）なので４は素数でありません。
ここでピンと来た方は素晴らしい。
２以外の偶数の約数は1と自分自身以外に必ず２があります。偶数は2の倍数ですから。ここで、総当たりしなければならない数が半分になります。
２以外の偶数は必ず合成数になるので、奇数のみ検討すればよいことになります。
さて、総当たりの限界はどのぐらいでしょうか。私は100前後までが限界です。
3. エラトステネスの篩
古代ギリシャのエラトステネスが提唱したのでこの名前になりました。
エラトステネスの篩ダウンロード
１は素数ではないので ❌をつけます。
次の数２は素数なので、 ⭕️をつけます。 2の倍数は素数でないので線で消しますが、ちょっとしたポイントがあります。 2の倍数は篩の 2の列全てです。さらに 4の列、 6の列、 8の列、 10の列も合成数なのでこれらを消すと次のよになります。
これで 2の倍数（偶数）は全て掃き出しました。
2の次の３は素数になります。 3の倍数は３から下に１左に 1移動した 12と 12 から同様に移動した 21です。さらに６を含め、下に 1左に 1と移動してゆき
51まで、 9から 81まで、 30から 93まで、 60から 96まで、 90から 99までとなります。
3 までの掃き出した結果は以下のようになります。
次の４は偶数なので、すべて掃き出されているので、その次の５が素数になります。 5の倍数は 5の列と 10の列ですが、 10の列はすでに掃き出されています。
次の素数は 7ですが、 7×2、 7×3、 7×5、７ ×(数 )はすでに掃き出されています。 残るのは7×7 、7×11 、7×13 なので、49 、77 、91 を× にします。
次の素数は 11ですが、ここで素数の重要な性質について簡単に触れなければなりません。この表では最大 100までの素数を見つけていますが、その場 √100＝ 10まで検討すればよいということです。 11の倍数は 11×11＝ 121でこの表の中にはありません。したがってこの表の中で残っている数は全て素数ということになります。
この表を元に、素数だけに丸をつけた表を作成します。
テキストで並べると
(2,3,5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,61, 67, 71, 73, 79,83, 89, 97)
となります。こうしてみると、素数は意外と多くあることがわかります。