素因数分解の計算

素因数分解のやり方(すだれ算)

素因数分解は「小さい素数から順に割っていく」だけでできます。割り算を縦に並べるすだれ算で書くと、間違えにくくなります。

手順

  1. 割り切れるいちばん小さい素数(2, 3, 5, 7, …の順に試す)で割る。
  2. 商(割った答え)を下に書き、また小さい素数から割る。
  3. 商が素数になったら止める。
  4. 左に並んだ割った数と、最後に残った商を全部掛け算の形にする。同じ数は指数でまとめる。

例: 360 を素因数分解する

236021802903453155

360 → 180 → 90 → 45 と 2 で 3 回割り、45 → 15 → 5 と 3 で 2 回割ると、5 が残ります。だから

360 = 2 × 2 × 2 × 3 × 3 × 5 = 23 × 32 × 5

100 万くらいまでの数がおすすめです(段が多いと図が長くなります)。

どの素数で割れるかの見分け方

割る素数 p が p × p > (今の商) になったら、今の商はもう素数です。たとえば 97 は √97 ≈ 9.8 なので、2, 3, 5, 7 で割り切れなければ素数と分かります。

約数の個数の求め方

n = pa × qb × rc と素因数分解できたら、約数の個数は

(a + 1) × (b + 1) × (c + 1) 個

です。約数は「2 を 0〜a 個、3 を 0〜b 個、… 選んで掛けた数」なので、選び方の数を掛け合わせます。360 = 2³ × 3² × 5 なら (3 + 1) × (2 + 1) × (1 + 1) = 24 個。

約数の総和は (1 + 2 + 4 + 8) × (1 + 3 + 9) × (1 + 5) = 15 × 13 × 6 = 1170 です。約数の一覧を出す計算もあります。

最大公約数・最小公倍数の求め方

素因数分解を使う

12 = 2² × 3、18 = 2 × 3² のとき、

ユークリッドの互除法を使う

大きな数では、割り算の余りを繰り返すほうが速く求まります。1071 と 1029 なら

1071 = 1029 × 1 + 42
1029 = 42 × 24 + 21
42 = 21 × 2 + 0

余りが 0 になる直前の割る数 21 が最大公約数です。最小公倍数は 1071 × 1029 ÷ 21 = 52479。最大公約数・最小公倍数の計算で確かめられます。

平方数にする・√ を簡単にする

素因数分解したとき、すべての指数が偶数なら平方数です。360 = 2³ × 3² × 5 は 2 と 5 の指数が奇数なので、2 × 5 = 10 を掛けると 3600 = 60² になります。同じ考えで √360 = √(6² × 10) = 6√10 です。

この計算サイトの仕組み

1 兆(10¹²)までは小さい数から順に割る試し割りで、すぐに答えが出ます。それより大きい数は、小さな素数で割ったあと、ポラードのロー法(ブレント版)で因数を探し、ミラー–ラビン判定で素数かを確かめます。ミラー–ラビン判定は最初の 13 個の素数を使うと 3.3×10²⁴ 未満で確実です。計算はすべてブラウザの中で行い、重い計算は画面を止めないよう別の処理(Web Worker)で動かします。