素数判定

整数が素数（1と自分自身でしか割り切れない数）かどうかを判定し、素数でなければ、計算の限度内で見つかる素因数を表示します。3,317,044,064,679,887,385,961,981未満の数は決定的ミラー–ラビン判定で処理するため、素数かどうかの答えは確率ではなく厳密です。入力した数の前後にある素数も表示します。

使い方

1. 整数を入力します。カンマとスペースは無視されます。
2. 素数か、合成数か、どちらでもない（0と1）かを確認します。
3. 合成数の場合は、素因数分解、最小の素因数、約数の個数を確認します。
4. 前の素数と次の素数で、最も近い素数を調べます。

計算式

n is prime ⇔ n > 1 and no prime p ≤ √n divides n

√nまで割ってみる試し割りが教科書的な方法です。大きいnには、2から41までの13個の素数を底とするミラー–ラビン判定を使い、3.3 × 10²⁴未満では誤りがないことが証明されています。合成数は試し割りとポラードのρ法で分解します。約数の個数は素因数分解から求まり、n = p₁^a × p₂^b × …なら約数は(a + 1)(b + 1)…個です。

計算例

91：√91 ≈ 9.5なので、2、3、5、7だけを調べれば十分です。91 ÷ 7 = 13なので、91は合成数で、91 = 7 × 13、約数は4個です。97：2、3、5、7のどれでも割り切れないので、97は素数で、前後の素数は89と101です。360 = 2³ × 3² × 5で、約数は(3 + 1)(2 + 1)(1 + 1) = 24個です。