素因数分解・最大公約数・最小公倍数を計算する(すだれ算・互除法つき)

整数を素因数分解し、素数かどうか、約数の個数・総和・一覧、√ を簡単にした形を出します。2〜10個の整数の最大公約数・最小公倍数は、素因数分解・すだれ算・ユークリッドの互除法の3通りの求め方を、途中の式つきで示します。24桁までの大きな数も、整数のまま正確に計算します。

制作:E-計算! 編集部(運営者情報・編集方針)。最終確認:。入力した数値は端末の中だけで計算し、送信しません。計算式と出典はページ末尾。

まず結論

条件を入力

例を入れる:

整数のまま計算します(小数で近似しません)。√ の値だけは小数4桁に四捨五入して表示します。

計算結果

素数と素因数分解

素数は、1とその数自身のほかに約数を持たない、2以上の整数です。2、3、5、7、11、13、17、19、… と続き、偶数の素数は2だけです。1は素数に入れません。2以上の整数のうち素数でない数(4、6、8、9、10、…)は合成数といい、いくつかの素数の積で表せます。

整数を素数の積で表すことを素因数分解といい、その積に出てくる素数を素因数といいます。1764 = 2 × 2 × 3 × 3 × 7 × 7 のように、同じ素数の積は累乗(指数)でまとめて、1764 = 22 × 32 × 72 と書きます。中学校の学習指導要領の解説は、素数でない数を約数の積に分ける操作を続けると最後は素数だけの積になり、「その表し方はただ一通りに決まる」としています。どの順に分けても、並べ替えれば同じ素数の積になります。

1を素数に入れない理由の1つは、この「ただ一通り」が成り立たなくなることです。1を素数とすると、6 = 2 × 3 = 1 × 2 × 3 = 1 × 1 × 2 × 3 のように、いくらでも別の分け方ができてしまいます。1は素数でも合成数でもない数です。

大きい数を素因数分解するには(√ まで割る)

素因数分解は、小さい素数から順に割っていくのが基本です。2で割れるだけ割り、次に3、5、7、11、13、…と、割り切れる素数を探します。割り算を縦に続けて書く方法をすだれ算(割り算の連続)といいます。1764 なら次のようになり、左に並んだ素数と、いちばん下に残った素数を掛けると、元の数に戻ります。

21764
2882
3441
3147
749
7

どこまで割ればよいかには目安があります。ある数 m が a × b(a ≤ b)と2つの数の積で表せるなら、a は √m 以下です。つまり、√m 以下の素数のどれでも割り切れなければ、m は素数です。1009 なら √1009 ≈ 31.76 なので、31 以下の素数(2、3、5、7、11、13、17、19、23、29、31 の11個)で割ってみて、どれでも割り切れないので素数と分かります。

割り切れるかどうかは、次の見分け方を使うと早く分かります。

  • 2……一の位が偶数(0、2、4、6、8)
  • 3……各位の数の和が3で割り切れる(6549 は 6 + 5 + 4 + 9 = 24 なので、3で割り切れる)
  • 5……一の位が0か5
  • 9……各位の数の和が9で割り切れる(1764 は 1 + 7 + 6 + 4 = 18 なので、9で割り切れる)
  • 11……一の位から1つおきに足した和と、残りの位の和との差が、0か11の倍数(253 は(3 + 2)− 5 = 0 なので、11で割り切れる)

たとえば、6549 は 3 × 2183 で、2183 は √2183 ≈ 46.72 以下の素数を順に試すと、37 で割り切れて 2183 = 37 × 59 になります(6549 = 3 × 37 × 59)。3721 は 2、3、5 では割り切れず、7、11、13、… と試すと 61 で初めて割り切れて、3721 = 612 です(√3721 がちょうど61)。253 は 11 × 23、323 は 17 × 19 で、323 は17より小さい素数では割り切れません。

約数の求め方(個数は「指数+1」を掛ける)

素因数分解ができると、約数の個数と総和が計算で求まります。1764 = 22 × 32 × 72 の約数は、2を0〜2個、3を0〜2個、7を0〜2個選んで掛けた数なので、約数の個数は (2 + 1) × (2 + 1) × (2 + 1) = 27個です。指数に1を足して掛けると個数になります。約数の総和は (1 + 2 + 4) × (1 + 3 + 9) × (1 + 7 + 49) = 7 × 13 × 57 = 5187 です。

約数を全部書き出すときは、表にすると漏れがありません。72 = 23 × 32 なら、2の累乗(1、2、4、8)と3の累乗(1、3、9)を1つずつ選んで掛け合わせます。

×139
1139
22618
441236
882472

72 の約数は 1、2、3、4、6、8、9、12、18、24、36、72 の12個((3 + 1) × (2 + 1) = 12)で、総和は195です。約数は「1 × 72、2 × 36、3 × 24、…」のように、掛けて72になる2つの数の組で探すこともできます。上の計算で素因数分解すると、「約数の一覧」に約数が小さい順に並びます(約数が1,000個までのとき)。素因数が2種類以上で、表が24行・6列に収まるときは、同じ形の表も出ます。

最大公約数・最小公倍数の求め方(3通り)

いくつかの整数に共通する約数を公約数、そのうちいちばん大きいものを最大公約数といいます。共通する倍数を公倍数、そのうちいちばん小さいものを最小公倍数といいます(0は倍数に含めません)。小学校の学習指導要領の解説の例では、8の約数は 1、2、4、8、12の約数は 1、2、3、4、6、12 なので、公約数は 1、2、4 で、最大公約数は4です。公倍数は 24、48、72、… で、最小公倍数は24です。

1. 素因数分解で求める

それぞれを素因数分解し、最大公約数は、すべての数に共通する素因数を、指数の小さい方で掛けます。最小公倍数は、どれかの数に出てくる素因数をすべて、指数の大きい方で掛けます。60・90・120 なら次のとおりです。

数235
602235
902325
1202335
最大公約数30235
最小公倍数36023325

最大公約数は 2 × 3 × 5 = 30、最小公倍数は 23 × 32 × 5 = 360 です。どれか1つの数にしかない素因数は、最大公約数には入りません。

2. すだれ算で求める

すべての数を割れる素数で割っていき、左に並んだ素数を掛けると最大公約数です。2つの数なら、左の素数といちばん下に残った数をすべて掛けると最小公倍数です。84 と 126 なら、最大公約数は 2 × 3 × 7 = 42、最小公倍数は 2 × 3 × 7 × 2 × 3 = 252 です。

284126
34263
71421
23

3. ユークリッドの互除法で求める

大きい方を小さい方で割り、次は割った数を余りで割る、という割り算を、余りが0になるまで続けます。最後に割った数が最大公約数です。a = b × q + r のとき、a と b の公約数と、b と r の公約数は同じなので、数を小さくしながら最大公約数を求められます。素因数分解しにくい大きな数でも、割り算だけで求まります。高等学校の数学Aの「数学と人間の活動」で、整数の約数や倍数とともに扱うとされている方法です。

1071 と 1029 なら、1071 = 1029 × 1 + 42、1029 = 42 × 24 + 21、42 = 21 × 2 + 0 で、最大公約数は21です。

2つの数では、最大公約数 × 最小公倍数 = 2つの数の積が成り立つので、最小公倍数は「2つの数の積 ÷ 最大公約数」で求まります。1071 × 1029 ÷ 21 = 52,479 です。60 と 90 でも、最大公約数30 × 最小公倍数180 = 5400 = 60 × 90 です。

3つの数のすだれ算は「2つだけ割れる」ときに注意

3つ以上の数の最小公倍数をすだれ算で求めるときは、すべての数を割れる素数がなくなったあとも、2つ以上の数を割れる素数があれば割り続けます。割れない数は、そのまま下に下ろします。どの2つの数も1以外の公約数を持たなくなったら終わりで、左の素数と、いちばん下の数をすべて掛けると最小公倍数です。

26090120
3304560
5101520
2234
132

60・90・120 では、2・3・5 ですべてを割ると 2、3、4 が残ります。ここで止めて 30 × 2 × 3 × 4 = 720 とするのは誤りです。2 と 4 はまだ2で割れるので、2 で割って 1、3、2 とし(3 はそのまま下ろす)、2 × 3 × 5 × 2 × 1 × 3 × 2 = 360 が最小公倍数です。最大公約数は、すべての数を割った 2 × 3 × 5 = 30 のままです。

また、「最大公約数 × 最小公倍数 = 積」は2つの数のときの関係です。60・90・120 では 30 × 360 = 10,800 ですが、積は 60 × 90 × 120 = 648,000 です。

最大公約数と最小公倍数から2つの数を求める

1以外の公約数を持たない2つの数を互いに素といいます。2つの数の最大公約数が12、最小公倍数が360なら、2つの数は 12 × x と 12 × y(x と y は互いに素)と書け、x × y = 360 ÷ 12 = 30 です。30 を互いに素な2つの数の積に分けると 1 × 30、2 × 15、3 × 10、5 × 6 なので、2つの数の組は、12 と 360、24 と 180、36 と 120、60 と 72 の4通りです。

√ を簡単にする(ルートの計算)

√ の中の数を素因数分解し、同じ素数が2つそろった組(2乗)を √ の外に出すと、√ を簡単にできます。72 = 23 × 32 = 62 × 2 なので、√72 = 6√2 です。1764 = 422 なので、√1764 = 42 と整数になります(平方数)。√2 や √6549 のように2乗の組がない数は、これ以上簡単になりません(√2 を 1√2 とは書きません)。

√簡単にすると小数(4桁)
√82√22.8284
√122√33.4641
√183√24.2426
√202√54.4721
√242√64.8990
√273√35.1962
√324√25.6569
√453√56.7082
√484√36.9282
√505√27.0711
√726√28.4853
√755√38.6603
√987√29.8995
√20010√214.1421

√ の中が平方数でなければ、√ の値は割り切れない小数(無理数)になります。このページは、√ の値を小数4桁に四捨五入して表示します(√72 ≈ 8.4853)。

大きな数の素数判定と、24桁までにしている理由

このページは、小さい素数(65,536 未満)で順に割る方法(試し割り)で、小さい素因数を見つけます。試し割りで決まらない大きな数は、ミラー–ラビン法という判定で、素数かどうかを確かめます。この判定は、決めた数(底)を使って「素数なら必ず成り立つ関係」を調べるもので、底の選び方によっては、合成数を素数と見誤ることがあります。

そこでこのページは、最初の13個の素数(2、3、5、7、11、13、17、19、23、29、31、37、41)を底にしています。この13個の底のすべてで見誤る合成数のうち、いちばん小さいものは 3,317,044,064,679,887,385,961,981(約3.3 × 1024)であることが、Sorenson と Webster の研究で示されています。24桁までの数(1024 未満)はこれより小さいので、判定の結果は必ず正しくなります。25桁の数の一部(約3.3 × 1024 以上)はこの範囲を超えるため、このページは24桁までにしています。

たとえば 561 = 3 × 11 × 17 は、「a560 を561で割った余りが1になるか」という簡単な判定(フェルマーの小定理を使う判定)では、561 と互いに素な数 a ならどれでも余りが1になり、素数のように見えてしまう数(カーマイケル数)です。ミラー–ラビン法では、底2で合成数と分かります。

大きな素因数は、小さい順に割る方法では時間がかかりすぎるため、別の方法で見つけ、実際に割り切れることを確かめています。結果は、素因数を掛けると元の数に戻ることと、上の判定で素因数が素数であることを確かめた値です。

この計算が扱わないこと

  • 負の数・小数・分数の素因数分解……素因数分解は2以上の整数で計算します。分数の約分は、分子と分母を2つの数として「最大公約数・最小公倍数」に入れると、結果に約分した分数が出ます。
  • 多項式の因数分解……x2 − 5x + 6 = (x − 2)(x − 3) のような式の因数分解はしません。
  • 25桁以上の数……25桁の数の一部(約3.3 × 1024 以上)は、素数かどうかを必ず正しく判定できる範囲(上の節)を超えるため、24桁までにしています。
  • 0……0 はどの数でも割り切れるので、素因数分解も、約数・倍数の計算もしません。

よくある質問

素因数分解のやり方を教えてください。
小さい素数から順に割っていきます。1764 なら、2で2回(1764 → 882 → 441)、3で2回(441 → 147 → 49)、7で1回割ると7が残るので、1764 = 2 × 2 × 3 × 3 × 7 × 7 = 2² × 3² × 7² です。割り算を縦に続けて書く「すだれ算」を使うと、割った素数が左に並びます。各位の数の和が3で割り切れれば3で割れる、などの見分け方を使うと早く見つかります。
1009 は素数ですか? どこまで割ればいいですか?
素数です。ある数が素数かどうかは、その数の平方根(√)以下の素数で割り切れるかを調べれば分かります。√1009 は約31.76なので、31 以下の素数 2、3、5、7、11、13、17、19、23、29、31 で割ると、どれも割り切れません。√ より大きい数で割り切れるなら、その商は √ より小さい数になり、その数の素因数で先に割り切れているはずなので、√ までで十分です。
1 は素数ですか?
いいえ。素数は、1とその数自身のほかに約数を持たない2以上の整数で、1は入りません。1を素数とすると、6 = 2 × 3 = 1 × 2 × 3 のように素因数分解がいくらでも作れてしまい、「素因数分解はただ一通り」という性質が成り立たなくなります。1は素数でも合成数でもない数です。
60・90・120 の最小公倍数は? すだれ算で720になってしまいます。
360です。すべての数を割れる2・3・5で割ると 2、3、4 が残りますが、ここで 30 × 2 × 3 × 4 = 720 としてはいけません。2 と 4 はまだ2で割れるので、2で割り(3はそのまま下ろす)、1、3、2 にします。最小公倍数は 2 × 3 × 5 × 2 × 1 × 3 × 2 = 360 です。素因数分解で 60 = 2² × 3 × 5、90 = 2 × 3² × 5、120 = 2³ × 3 × 5 の指数の大きい方を掛けた 2³ × 3² × 5 = 360 とも一致します。
3つの数の最大公約数はどう求めますか?
すべての数に共通する素因数を、指数の小さい方で掛けます。60・90・120 なら 2 × 3 × 5 = 30 です。すだれ算なら、3つの数すべてを割れる素数で割れるだけ割り、左に並んだ素数を掛けます。互除法なら、まず2つの数の最大公約数を求め(60 と 90 で30)、その数と3つ目の数の最大公約数を求めます(30 と 120 で30)。
ユークリッドの互除法とは何ですか?
2つの数の最大公約数を、割り算をくり返して求める方法です。大きい方を小さい方で割り、次は割った数を余りで割る、を余りが0になるまで続け、最後に割った数が最大公約数です。1071 と 1029 なら、1071 = 1029 × 1 + 42、1029 = 42 × 24 + 21、42 = 21 × 2 + 0 で、最大公約数は21です。最小公倍数は 1071 × 1029 ÷ 21 = 52,479 です。
素因数分解から約数を全部出すには? 約数の個数は?
素因数の累乗を組み合わせて掛けます。72 = 2³ × 3² なら、2の累乗(1、2、4、8)と3の累乗(1、3、9)を1つずつ選んで掛けた 1、2、3、4、6、8、9、12、18、24、36、72 が約数です。個数は、指数に1を足して掛けた (3 + 1) × (2 + 1) = 12個です。1764 = 2² × 3² × 7² なら (2 + 1) × (2 + 1) × (2 + 1) = 27個です。
最大公約数と最小公倍数から、2つの数を求めるには?
最大公約数を g とすると、2つの数は g × x と g × y(x と y は互いに素)と書け、x × y は 最小公倍数 ÷ g です。最大公約数12・最小公倍数360なら x × y = 30 で、互いに素な組は 1 と 30、2 と 15、3 と 10、5 と 6 なので、2つの数は 12 と 360、24 と 180、36 と 120、60 と 72 の4通りです。
√72 を簡単にするには?
√ の中を素因数分解して、2乗の組を √ の外に出します。72 = 2³ × 3² = 6² × 2 なので、√72 = 6√2(約8.4853)です。1764 = 42² なので、√1764 = 42 です。√2 のように2乗の組がない数は、これ以上簡単になりません。
「最大公約数 × 最小公倍数 = 2つの数の積」は、3つの数でも成り立ちますか?
成り立ちません。2つの数 a、b では、最大公約数 × 最小公倍数 = a × b です(60 と 90 なら 30 × 180 = 5400 = 60 × 90)。3つの数 60・90・120 では、最大公約数30 × 最小公倍数360 = 10,800 で、3つの数の積の 648,000 とは違います。

関連するツール

計算式と出典

素因数分解は、小さい素数から順に割る試し割り(65,536 未満の素数)と、大きな素因数を見つける別の計算で行い、見つけた素因数は、掛けると元の数に戻ることと、素数であることを確かめています。素数かどうかは、試し割りで決まらない数について、最初の13個の素数を底にしたミラー–ラビン法で判定します(3,317,044,064,679,887,385,961,981 未満で正しいことが上の論文で示されているため、24桁までの数では必ず正しい結果になります)。約数の個数 = (指数 + 1) の積、約数の総和 = (1 + p + … + pe) の積、最大公約数 = 共通の素因数の小さい方の指数の積、最小公倍数 = 出てくる素因数の大きい方の指数の積です。互除法は a = b × q + r をくり返し、2つの数の最小公倍数は 積 ÷ 最大公約数、3つ以上は2つずつ順に求めます。計算はすべて整数のまま行い、√ の値だけを小数4桁に四捨五入して表示します。入力は整数だけを受け付け、小数・分数・単位の付いた値や、3桁区切りでないカンマ(60,90 など)は読み替えずに知らせます。