2026-01-26…数学…エラトステネスのふるい
目次
はじめに
中学数学の復習をしていたら知らない用語が出てきた。「エラトステネスのふるい」といい、どうやら素数を効率的に見つける方法らしい。
この方法を使うと、ある数までの素数を見つけたい場合、例えば「100」までの素数を見つけたい場合、「√100」つまり「10」までの素数を見つければいいらしい。
ずるい、超べんり。なんで教えてくれなかったんだろう。いや、聞いてなかっただけかも……。
エラトステネスのふるい
概要
ある整数までの素数を効率よく見つけるための方法。
小さい素数の倍数を消していくと、残った数が全て素数という便利な方法。
しかも見つける素数は「√N」まででよい。（ある数「N」までの素数を見つけたい場合）
手順
1～100までの素数を見つけたい場合。
「1～100」までの整数を並べる。
「1」は素数ではないので消す。
始めの素数である「2」を残し、「2」の倍数を消す。
次の素数である「3」を残し、「3」の倍数を消す。
次の素数である「5」を残し、「5」の倍数を消す。
これを「√100」つまり「10」を超えるまで続ける。
（素数を見つける範囲が「1~N」なら「√N」を超えるまで）
残っている数がすべて素数。
つぶやき
学生の時にちゃんと勉強しておけばと後悔する人が多いと聞くけど、本当かな？
自分はそんなに後悔していない。そのぶん遊んでいたから。しかし、その遊びが何かの役に立ったのかというと……。
勉強はツマラナイから、なにか目的が必要だよね。
自分の知り合いで、学生の時から将来の仕事を決めていた人は、全員その仕事についている。
うらやましいと思うけど、当時から努力して勉強していた。だから、うらやましいなんて言うと、きっと怒るだろうな。