素因数分解

数を素数の積として表し、それ自体が素数かどうかをすぐに確認できます。

計算式数学

この数は合成数です。1 と自分自身以外の約数があります。

仕組み

1 より大きいすべての整数は、順序を除けば、素数の積として一通りに表せます。計算機はまず小さい素数で割り切り、次に Pollard のロー法を用いて大きい因数を分解します。

それぞれの因数が素数であることは、決定的な Miller–Rabin 判定法で確認されます。この大きさの数に対しては、その正しさが証明されています。約数の個数は指数から求められます。各指数に 1 を足して、それらを掛け合わせます。

n = p₁^a₁ × p₂^a₂ × … × pₖ^aₖ
約数の個数 = (a₁ + 1)(a₂ + 1)…(aₖ + 1)

360 = 2 × 2 × 2 × 3 × 3 × 5 = 2³ × 3² × 5 です。約数の個数は (3 + 1)(2 + 1)(1 + 1) = 24 です。近くの素数は 359 と 367 です。

1 は素数ですか？

いいえ。素数の約数はちょうど二つ、1 と自分自身です。1 の約数は一つだけです。1 を除外しておくと、素因数分解の結果が一通りに定まります。

2 は唯一の偶数の素数ですか？

はい。他のすべての偶数は 2 で割り切れるため、少なくとも三つの約数を持ちます。

大きな数が素数かどうかはどのように確認しますか？

大きな数では試し割りでは遅すぎるため、Miller–Rabin などの判定法が使われます。適切な底を選べば、この大きさの数について確実な答えが得られます。