素数判定機
数を入力して素数かどうか判定し、範囲内の素数一覧や素因数分解の結果を求めます。
素数について
素数とは、1と自分自身以外に正の約数を持たない、1より大きい自然数のことです。
試し割り法：2から√n以下の数で割り切れなければ素数です。
素数は無限に存在します：2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 ...
計算例
97は素数です。√97 ≈ 9.85以下のどの数でも割り切れないため、約数は1と97だけです。
1から50までの素数は15個あります。2、3、5、7、11、13、17、19、23、29、31、37、41、43、47です。
この判定の限界
意味があるのは2以上の整数だけです。1は素数でも合成数でもなく、0と負の数は対象外です。平方根まで割る方法は正確ですが非常に大きな数では遅くなるため、暗号ではミラー・ラビンなどの確率的テストを使います。
よくある質問
- 1が素数でないのはなぜですか
- 素数は約数をちょうど2つ（1と自分自身）持つ数です。1は約数が1つしかなく、1を除くことで素因数分解の一意性が保たれます。
- 素数はいくつありますか
- 無限にあります。既知の素数をすべて掛けて1を足した数は、どの素数でも割り切れないため、さらに大きな素数が必ず存在します（ユークリッドの証明）。
- 平方根まで調べれば十分なのはなぜですか
- n = a × bなら、2つの因数のうち少なくとも一方は√n以下です。したがって√nまで割り切れる数がなければ、それ以上にも存在しません。