素因数分解・GCD・LCM
暮らし
1 つまたは 2 つの正整数を入力。それぞれについて: `p^e × q^f` 形式の素因数分解、すべての約数、その数自体が素数かどうか。両方入力すると、GCD（最大公約数 — 分数の約分に有用）と LCM（最小公倍数 — 共通周期を見つけるのに有用）も得られる。√n までの試し割りは ~10¹² までの数に対して十分速く、すべてブラウザ内で実行。
—
GCD (最大公約数)
36
LCM (最小公倍数)
2520
360
素因数分解
2^3 × 3^2 × 5
約数 (24)
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 72, 90, 120, 180, 360
252
素因数分解
2^2 × 3^2 × 7
約数 (18)
1, 2, 3, 4, 6, 7, 9, 12, 14, 18, 21, 28, 36, 42, 63, 84, 126, 252
√n までの試し割り。~10¹² までの入力に高速。応答性のため 10⁹ 超では約数スキャンをスキップ。
使い方
- フィールド A に数を入力 — 素因数分解、約数、素数判定。
- フィールド B に 2 つ目を追加すると GCD・LCM も計算。
- 素因数分解をコピー、または約数リストを確認。非常に合成された数では約数リストは最初の 200 個に制限。
よくある質問
- 最大入力は？
- 約 10¹²（兆）まで。それ以上では JavaScript が整数精度を失い（Number.MAX_SAFE_INTEGER は 2⁵³ ≈ 9×10¹²）、√n までの試し割りも遅くなる。より大きな数には BigInt と Pollard's rho が必要。
- なぜ大きな数で約数リストがない？
- CPU 過負荷を避けるため、約数スキャンは n < 10⁹ で打ち切る。素因数分解は最大の素因数まで O(√n) であり、しばしば n よりはるかに小さいため依然動作する。
- GCD は何の役に立つ？
- 分数の約分: 252/360 = ?。GCD(252, 360) = 36 なので 252/360 = 7/10。暗号学（RSA）、2 つのサイクルがいつ一致するかの判定にも使用。
- LCM(a, b) = a × b / GCD(a, b)？
- はい、常に、正整数について。まさにこの恒等式を使用。直感: LCM は a と b に現れる各素因数の最高冪、GCD は各素因数の最低冪を持ち、掛け合わせると a × b になる。