numbers 素数一覧・判定ツール star

使い方

このツールは、それぞれ異なる問いに答える2つのアルゴリズムを切り替えて使用します。リストモードは、今でも日常的に使われている最古のアルゴリズムの一つであるエラトステネスの篩を用いて、指定した上限までのすべての素数を見つけます(紀元前3世紀のギリシャの数学者エラトステネスに由来するとされています)。2から始めて2のすべての倍数を合成数として消していき、次に消されていない数(3)に進んでその倍数を消し、次に消されていない数(5)に進む、という具合に続けます。上限の平方根に達した時点で消されずに残っている数がすべて素数です。小さな例:30まで篩にかける場合、まず2の倍数(4,6,8,…)を消し、次に3の倍数(6,9,12,…、一部はすでに消済み)を消し、次に5の倍数(10,15,…)を消します — 5×5=25 ≤ 30ですが7×7=49 > 30なので、そこで止められます。残るのは2, 3, 5, 7, 11, 13, 17, 19, 23, 29で、これが完全なリストです。この処理はO(n log log n)の計算量で動作するため、範囲が数十万に広がっても高速さを保ちます。

判定モードは別の問い — この特定の数は素数か? — に答えるもので、平方根までの試し割りを使います。nが素数かどうかを調べるには、2から√nまでの約数を確認すれば十分です。理由はこうです:もしn = a × bで、aとbの両方が√nより大きいとすると、a × bはnより大きくなってしまい、矛盾します。したがって2つの因数のうち少なくとも一方は√n以下でなければならず、ループが終わる前に見つかります。例:97を調べるには2, 3, 5, 7で割り切れるかを確認するだけで十分です(9²=81 ≤ 97ですが10²=100 > 97のため) — どれも割り切れないため、97は素数です。

知っておくべきこと

この2つのモードが存在するのは、それぞれトレードオフが異なるためです:篩は一度に多数の素数を生成するのに効率的ですが、巨大な上限付近の1つの数だけに関心がある場合はメモリと時間を無駄にします。試し割りは1回の判定には効率的ですが、大きな範囲のすべての数に対して1つずつ繰り返すには遅すぎます。用途に応じて適切な方を選べるようにするために、このツールは両方を提供しています。

• 1は定義と慣習により素数から除外されています — 約数が2つではなく1つしかなく、もし素数に含めると素因数分解の一意性が崩れてしまうためです。
• 2は唯一の偶数の素数です。それ以外のすべての偶数は2で割り切れるため合成数です。
• 数が大きくなるにつれて素数は平均的に希少になっていきますが、決して現れなくなることはありません — ユークリッドは2000年以上前に、素数が無限に存在することを証明しました。