素因数分解のやり方(すだれ算)
素因数分解は「小さい素数から順に割っていく」だけでできます。割り算を縦に並べるすだれ算で書くと、間違えにくくなります。
手順
- 割り切れるいちばん小さい素数(2, 3, 5, 7, …の順に試す)で割る。
- 商(割った答え)を下に書き、また小さい素数から割る。
- 商が素数になったら止める。
- 左に並んだ割った数と、最後に残った商を全部掛け算の形にする。同じ数は指数でまとめる。
例: 360 を素因数分解する
360 → 180 → 90 → 45 と 2 で 3 回割り、45 → 15 → 5 と 3 で 2 回割ると、5 が残ります。だから
360 = 2 × 2 × 2 × 3 × 3 × 5 = 23 × 32 × 5
どの素数で割れるかの見分け方
- 2: 一の位が偶数(0, 2, 4, 6, 8)
- 3: 各位の数の和が 3 の倍数(360 なら 3 + 6 + 0 = 9)
- 5: 一の位が 0 か 5
- 7・11・13 などは実際に割ってみる
割る素数 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² のとき、
- 最大公約数は、共通の素数を小さいほうの指数で掛ける: 2¹ × 3¹ = 6
- 最小公倍数は、出てくる素数を全部大きいほうの指数で掛ける: 2² × 3² = 36
ユークリッドの互除法を使う
大きな数では、割り算の余りを繰り返すほうが速く求まります。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)で動かします。