素数判定ツール

ステップ 1 / 2 数値

数値

次へ

整数を入力すると、素数かどうかを判定します。2未満の値は素数ではないとし、まず2で割り切れるかを確認してから、平方根までの奇数の約数を順に試します。正の合成数の場合は素因数分解も表示します。

判定の仕組み

1

入力を検証

先頭にマイナス記号を1つ付けた10進数字を入力できます。値はPHPの整数型に収まる必要があります。
2

小さい値を処理

2未満は素数ではなく、2は素数、2より大きい偶数はすべて合成数です。
3

奇数の約数を試す

正の奇数について、3、5、7と順にfloor(sqrt(n))まで割り切れるかを調べます。
4

結果を表示

正の合成数には素因数も表示し、素数の場合はそのまま結果を知らせます。

判定例

入力	結果	追加表示
-7	素数ではない	なし
0	素数ではない	なし
1	素数ではない	なし
2	素数	なし
49	素数ではない（7で割り切れる）	`素因数: 7 × 7`
97	素数	なし
100	素数ではない（2で割り切れる）	`素因数: 2 × 2 × 5 × 5`

判定方法と制限

試し割り法による判定であり、Miller–Rabin法や確率的素数判定ではありません。
ブラウザのBigIntではなく、サーバー側のPHP整数型を使います。その範囲を超える入力を確実に扱うことはできません。
実行時間は入力値の平方根に応じて増えます。大きな素数や、大きな因数を持つ合成数では時間がかかる場合があります。
負の値、0、1は素数ではないと判定します。負の値を絶対値に置き換えることはありません。
入力値の前後にある最も近い素数は検索しません。

データの取り扱い

通常の判定は当社のサーバーで行われるため、ボタンを押すと入力値がサーバーへ送信されます。2段階表示では数値がページのURLに含まれます。秘密の値を入力しないでください。

よくある質問

素数とは、1とその数自身という2つの正の約数だけを持つ、1より大きい正の整数です。

対応範囲内の入力については決定的です。試し割り法は明確な答えを返し、確率的な判定は使いません。

サーバーのPHP整数型に収まる必要があります。ただし試し割りは、その数値上の上限に達するよりかなり前に、実用上遅すぎる場合があります。

対応する正の合成数については素因数の文字列を表示します。展開形と指数表記を詳しく見たい場合は、素因数分解計算ツールを使用してください。

関連ツール

このツールは他の言語でも利用できます