この計算機でできること
このツールは、入力した整数が素数か合成数かを判定します。素数とは1より大きい数のうち、約数が「1」と「その数自身」のちょうど2つだけのものを指します。一方、合成数はそれ以外の約数を少なくとも1つ持つ数です。なお0と1は素数でも合成数でもないため、この計算機には2以上の数を入力してください。
使い方
入力欄に好きな整数を入力して送信するだけです。計算機が素数か合成数かを判定し、合成数の場合は最小の素因数と因数分解の例（最小の約数 \(\times\) 対応するもう一方の約数）もあわせて表示します。
計算の仕組み
判定には「試し割り」という方法を使います。ある数 n が合成数かどうかを調べるには、2から n の平方根までの約数 d を試すだけで十分です。その範囲のいずれかの d で n が割り切れれば、n は合成数です。どれでも割り切れなければ素数となります。√n までの確認で済むのは、\(n = a \times b\) と表せるとき、少なくとも一方の因数は必ず √n 以下になるからです。
$$\text{Prime if } \text{n} > 1 \text{ and } \nexists\, d \in [2, \lfloor\sqrt{\text{n}}\rfloor] : \text{n} \bmod d = 0$$ $$\begin{gathered} \text{Classify}(\text{n}) = \begin{cases} \text{Prime} & \nexists\, d \in [2,\lfloor\sqrt{\text{n}}\rfloor],\; \text{n} \bmod d = 0 \\[0.4em] \text{Composite} & \exists\, d \in [2,\lfloor\sqrt{\text{n}}\rfloor],\; \text{n} \bmod d = 0 \\[0.4em] \text{Neither} & \text{n} < 2 \end{cases} \end{gathered}$$
具体例で確認
n = 91 で考えてみましょう。91の平方根は約9.54なので、2、3、5、7、9を試します。すると \(91 \div 7 = 13\) でちょうど割り切れるため、91は合成数で、最小の約数は7、因数分解は \(7 \times 13\) となります。一方、97は9までのどの数でも割り切れないため、素数です。
よくある質問
1は素数ですか？ いいえ。定義上、素数は異なる正の約数をちょうど2つ持つ必要がありますが、1の約数は1つだけです。
2は素数ですか？ はい。2は唯一の偶数の素数です。
なぜ平方根までで止めるのですか？ √n より大きい約数は、必ず √n より小さい約数とペアになっています。その小さい方はすでに調べ終えているため、√n を超えて確認するのは無駄になるからです。
