結果の見方
下の表は、サンプル入力に対する3つの出力を示しています。
| 入力 | 素数？ | 素因数分解 | 次の素数 |
|---|---|---|---|
| 97 | はい | 97 | 101 |
| 84 | いいえ | 2 × 2 × 3 × 7 | 89 |
| 100 | いいえ | 2 × 2 × 5 × 5 | 101 |
| 2 | はい（唯一の偶数の素数） | 2 | 3 |
| 1 | いいえ（素数でも合成数でもない） | - | 2 |
- 1は素数ではありません。素数は正確に2つの異なる約数を持つ必要がありますが、1の約数は1つだけです。1を除外することで、素因数分解の一意性が保たれます。
- 試し割り法は正確ですが、非常に大きな入力では処理が遅くなります。この計算機は10^12までの数を受け付け、その探索では最大100万までの約数を調べます。
- この範囲では、次の素数の探索は必ずすぐに終了します。ベルトランの仮説により、nと2nの間には常に素数が存在するからです。
素数とは？
素数とは、1より大きい自然数で、正の約数がちょうど2つ、すなわち1とその数自身だけであるものです。最初の素数は2、3、5、7、11、13、17、19、23、29です。2は唯一の偶数の素数です。他の偶数はすべて2で割り切れるからです。1より大きく素数でない数は合成数と呼ばれます。1は定義上、素数でも合成数でもありません。
算術の基本定理により、1より大きいすべての整数は、因数の順序を除いてただ一通りの方法で素数の積として表せます。この一意な素因数分解こそが、素数が整数の構成要素と呼ばれる理由です：84 = 2² × 3 × 7であり、他のどんな素数の組み合わせを掛けても84にはなりません。
素数の個数は無限であり、これは紀元前300年頃にユークリッドが証明した結果です。数が大きくなるにつれて素数はまばらになりますが、単純な規則性はありません。大きな素数は、現代の公開鍵暗号（RSAなど）の基盤となっており、これは2つの非常に大きな素数の積を実用上因数分解することが困難であることに依拠しています。
この素数計算機の使い方
- 1以上の整数nを入力します。小数は最も近い整数に切り捨てられます。
- 素数判定の結果を確認します。チェックマークはその数が素数であることを、バツ印は合成数（または素数でも合成数でもない1）であることを示します。
- 素因数分解を確認します。これは、入力した数に等しくなる一意な素数の積です。入力が素数の場合、素因数分解はその数自身になります。
- 次の素数、つまり入力した数より真に大きい最小の素数を確認します。
素数判定の方法：試し割り法
数nが合成数であるための必要十分条件は、1より大きくnの平方根以下の約数を持つことです。これは、約数がペアになるためです：n = a × b（a ≤ b）ならば、a ≤ √nです。したがって、試し割り法では候補の約数を√nまでだけ調べればよく、2を確認した後は奇数の候補だけを調べれば十分です。
計算例（素数の場合）：n = 97。97の平方根はおよそ9.85なので、2、3、5、7、9を調べれば十分です。97は奇数です。9 + 7 = 16は3で割り切れません。0や5で終わっていません。97 / 7 = 13.857…。97 / 9も整数になりません。約数が見つからないため、97は素数です。
計算例（素因数分解）：n = 84。小さい素数から順に割っていきます：84 / 2 = 42、42 / 2 = 21、21 / 3 = 7、そして7は素数です。したがって84 = 2 × 2 × 3 × 7 = 2² × 3 × 7です。84の次の素数は89です（85 = 5 × 17、86 = 2 × 43、87 = 3 × 29、88 = 2³ × 11）。
よくある間違い
- 1を素数として数えてしまうこと。定義上、素数はちょうど2つの異なる約数を持ちますが、1の約数は1つだけです。
- すべての素数が奇数だと思い込むこと。2は素数であり、唯一の偶数の素数です。
- √nで止めずに、約数をnまですべて調べてしまうこと。合成数には必ずその平方根以下に因数があります。
- すべての奇数が素数だと信じてしまうこと。9 = 3 × 3、15 = 3 × 5、21 = 3 × 7はいずれも奇数の合成数です。
- 素因数分解と単なる因数分解を混同すること。84 = 4 × 21も因数分解の一つですが、素因数分解は2 × 2 × 3 × 7です。
よくある質問
ある数が素数かどうかはどうやって確認しますか？
2からその数の平方根までの整数のいずれかで割り切れるかを調べます。どれでも割り切れなければ、その数は素数です。97の場合、平方根はおよそ9.85で、2、3、5、7、9のいずれでも97は割り切れないため、97は素数です。約数はペアになるため、合成数には必ずその平方根以下に因数が存在します。
なぜ1は素数ではないのですか？
素数は、正確に2つの異なる正の約数、すなわち1とその数自身を持つものと定義されています。1の約数は1つだけです。この定義は算術の基本定理も守っています。もし1が素数だとすると、素因数分解は一意ではなくなってしまいます（6 = 2 × 3 = 1 × 2 × 3 = 1 × 1 × 2 × 3、というように）。
素因数分解とは何ですか？
ある数を素数の積として表したものであり、算術の基本定理により、順序を除いて一意であることが保証されています。例えば、84 = 2 × 2 × 3 × 7です。求め方は、割り切れる最小の素数で繰り返し割っていき、商が1または素数になるまで続けます。
2は素数ですか？
はい。2の約数は1と2だけなので素数であり、唯一の偶数の素数です。他の偶数はすべて2で割り切れるため合成数です。これが、素数判定で2だけを別扱いし、それ以外は奇数の候補だけを調べる理由です。
素数はいくつありますか？
無限に存在します。これは紀元前300年頃にユークリッドが証明しました。任意の有限個の素数のリストが与えられたとき、それらすべてを掛け合わせて1を足した数は、そのリストのどの素数でも割り切れません。つまり、リストから漏れた素数が存在することになります。数が大きくなるにつれて素数はまばらになります。素数定理によれば、n付近の素数の密度はおよそ1 / ln(n)ですが、素数が尽きることはありません。
なぜ素数は暗号において重要なのですか？
RSAのような公開鍵方式は、非対称性に基づいています。2つの大きな素数を掛け合わせるのは簡単ですが、実用上使われる規模（数百桁）では、その積から元の素数を求めることは計算上非常に困難です。セキュリティ鍵はこうした積から構築されるため、素数の生成と素数判定は暗号の中核的な操作です。
参考文献
- Weisstein, Eric W. 「Prime Number」および「Fundamental Theorem of Arithmetic.」 MathWorld — A Wolfram Web Resource. mathworld.wolfram.com.
- Hardy GH, Wright EM. An Introduction to the Theory of Numbers. Oxford University Press (primes, unique factorization, Bertrand's postulate).
- Euclid. Elements, Book IX, Proposition 20 (infinitude of primes).