素因数分解・最大公約数

Factors, GCD & LCM

整数を素因数分解し、複数の数の最大公約数・最小公倍数・約数・素数判定を計算します。

整数を素因数に分け、約数、約数の和、オイラーのφ、前後の素数を伝えます。複数の数を渡せば最大公約数と最小公倍数を計算します。計算はどの大きさでも正確なので、2^53を超える数も正しく振る舞います。

🔒 ブラウザの中だけで動きますmathprimegcdnumber-theory

数をひとつ

数

大きさに制限はありません。ここでの計算はすべて正確な整数演算なので、表計算ソフトが連続する整数を区別できなくなる 2^53 を超える数もきちんと扱えます。

素因数分解

360 = 2^3 × 3^2 × 5

素数か

いいえ

桁数

約数の個数

約数の和

1,170

オイラー φ

その数より小さい互いに素な数の個数

完全数か

いいえ

自分自身を除く約数の和に等しい数

次の素数

367

前の素数

359

約数（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

数を複数

最大公約数

最小公倍数

5,040

1 行に 1 つずつ、またはカンマで区切って。

素数判定は確率ではなく証明です。ミラー–ラビン法は一般には確率的な検査ですが、最初の 13 個の素数を底に使えば 3.3 × 10²⁴ 未満に例外となる合成数が存在しないことが証明されています。ここに入力できるどんな数よりも十分に大きい範囲です。大きな合成数は試し割りのあとポラードのロー法で分解します。15 桁の素数 2 つの積がミリ秒で割れるのはそのためです。

使い方

数をひとつ入力します
数字だけでも、カンマを入れても構いません。素因数分解、約数、素数かどうかの判定がまとめて出ます。
または複数入れて最大公約数と最小公倍数を求めます
1行に1つか、カンマ区切りです。分数をまとめて約分するときや、繰り返しの周期を求めるときに使うのがこのパネルです。
素数が要るときは前後の素数を見ます
次の素数と前の素数を表示します。ハッシュテーブルや法として、ある大きさの近くの素数が欲しいときに探しているのがそれです。

よくある質問

大きい数を断られました。なぜですか。

素数かどうかを調べるのはどの大きさでも速いのですが、分解するほうが高くつきます。ポラードのロー法はおおよそその数の4乗根に比例する時間がかかり、20桁ならミリ秒、40桁を超えると数秒かかります。しかもブラウザが割り込めない1回の呼び出しの中でです。タブを固まらせる代わりに途中でやめ、それでもその数が素数かどうかは伝えます。