ヅラッシュ！ by NI-Lab.

C言語の学習用に素数のリストを作成するプログラムを書いた。たぶん3年前。

数値が素数であるかチェックする方法: 対象数値未満の整数(1を除くすべて)で割り切れなければ素数。って、1001が素数であるかを調べるには最高で1000回の計算をしなければいけない……2 * 500 = 1000 だから 500 以上で割るプロセスは無駄になるし……効率がすばらしく悪い。

そこで、知人に教えを請うたところ「割り切れる数値にフラグを立てる」というアルゴリズムを紹介してくれた。対象の数値が素数であるかチェックするのではなく、素数でない数値にフラグを立てていく。この手法は知人のオリジナルだと思いこんでいたのだが……

久々にそんなことを調べていたら IDM | 素因数分解 | エラトステネスの篩い なるページを見つけた。先の手法は「エラトステネスの篩い」という「最も古典的な素数表作成アルゴリズム」であるらしい。数学っておもしろそうだなぁ。