素因数分解と最大公約数
素因数分解・最大公約数・最小公倍数・約数の個数をまとめて出します。
素因数分解は試し割りで行い、√nまで割り切れる数を探します。18桁までの数なら一瞬で終わります。最大公約数はユークリッドの互除法で、これは紀元前300年頃の『原論』に載っている手順が今もそのまま最速の部類にあるという珍しい例です。約数の個数は素因数分解から出るので、割り算を繰り返す必要はありません。
数
二つでも多数でも。正の整数のみです。
約数と倍数
最大公約数
6
最小公倍数
5,040
それぞれの数
| 数 | 素因数 | 約数の個数 | 素数 |
|---|---|---|---|
| 48 | 2^4 × 3 | 10 | いいえ |
| 180 | 2^2 × 3^2 × 5 | 18 | いいえ |
| 210 | 2 × 3 × 5 × 7 | 16 | いいえ |
共通の素因数を最も低い指数で取ると最大公約数、すべての素因数を最も高い指数で取ると最小公倍数になります。
安全な整数の範囲(約9,007兆)を超える値では精度が落ちることがあります。
48・180・210を手で解くと
初期値の三つを素因数分解すると 48 = 2⁴×3、180 = 2²×3²×5、210 = 2×3×5×7 です。三つすべてに含まれる素因数は2と3で、低いほうの指数を取ると 2×3 = 6、これが最大公約数です。最小公倍数は現れた素因数をすべて高いほうの指数で集めた 2⁴×3²×5×7 = 5,040 です。表の約数の個数は各指数に1を足して掛けた値なので、48は (4+1)(1+1) = 10個、180は 3×3×2 = 18個、210は 2⁴ = 16個になります。
最大公約数は素因数分解なしで出します
画面はユークリッドの互除法を使います。大きいほうの数を小さいほうで割った余りに置き換え、余りが0になるまで繰り返す手順です。180と48なら 180 = 3×48 + 36、48 = 1×36 + 12、36 = 3×12 + 0 なので12です。数が三つ以上あれば、その結果と次の数をまた入れます — gcd(12, 210) = 6。最小公倍数も同じように二つずつ進みます。lcm(48, 180) = 48×180÷12 = 720、lcm(720, 210) = 720÷30×210 = 5,040。掛ける前に先に割るので、大きな数でも途中の値が溢れにくくなります。
素因数は平方根まで探せば足ります
nの素因数のうち√nより大きいものは多くても一つです。そこで2と3を先に取り除き、5, 7, 11, 13, … のような 6k±1 の形だけを√nまで試し、1より大きいものが残ればそれが最後の素因数です。1,000,000,007 のような十桁の素数も、3万回あまりの割り算で終わります。「素数」の列が「はい」の数は素因数が自分自身だけの数で、約数は1と自分自身の二つです。1は素数ではなく、素因数分解も空になります。
入力をどう読むか
カンマ・セミコロン・空白・改行のどれで区切っても構いません。小数点があれば切り捨てて整数だけを残し(3.7 → 3)、0と負の数は計算から外します。数が一つだけなら最大公約数も最小公倍数もその数自身です。数が二つ以上で最大公約数が1なら、互いに素だと知らせます。最小公倍数はすぐ大きくなるので、約9,007兆(2⁵³)を超えると末尾の桁は信用できません — 互いに素な八桁の数二つの積で、もうその辺りです。
よくある質問
Qどれくらい大きな数まで扱えますか
素因数分解は概ね15桁までなら実用的な速さで終わります。それを超えると、二つの大きな素数の積である場合に時間がかかります — RSA暗号が成り立っているのはまさにこの困難さのおかげなので、遅いのは不具合ではありません。最大公約数と最小公倍数はもっと大きな数でも一瞬です。
Q約数の個数はどう出しますか
素因数分解の各指数に1を足して掛け合わせます。12 = 2²×3¹ なら (2+1)(1+1) = 6個です。実際に1から12まで割ってみても6個で一致します。この画面は個数だけでなく約数そのものも並べます。
Q最小公倍数が大きすぎて表示が崩れます
最小公倍数は二数の積を最大公約数で割った値なので、互いに素な大きい数どうしだと桁が急に増えます。計算は倍精度の数で行うため、2⁵³(約9,007兆)を超えると末尾が正確でなくなります — その手前までは合っています。