素因数分解・最大公約数・最小公倍数を計算する(すだれ算・互除法つき)
整数を素因数分解し、素数かどうか、約数の個数・総和・一覧、√ を簡単にした形を出します。2〜10個の整数の最大公約数・最小公倍数は、素因数分解・すだれ算・ユークリッドの互除法の3通りの求め方を、途中の式つきで示します。24桁までの大きな数も、整数のまま正確に計算します。
- 素因数分解は、小さい素数から順に割ります(2、3、5、7、11、…)。1764 = 2 × 2 × 3 × 3 × 7 × 7 = 22 × 32 × 72 です。
- √ 以下の素数で割り切れなければ、素数です。1009 は √1009 ≈ 31.76 なので、31 以下の素数で割り切れないことを確かめれば素数と分かります。
- 最大公約数は、共通の素因数を小さい方の指数で、最小公倍数は、出てくる素因数を大きい方の指数で掛けます。60・90・120 の最大公約数は30、最小公倍数は360です(720ではありません)。
計算結果
約数の一覧
計算式と内訳
素数と素因数分解
素数は、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 なら次のようになり、左に並んだ素数と、いちばん下に残った素数を掛けると、元の数に戻ります。
| 2 | 1764 |
| 2 | 882 |
| 3 | 441 |
| 3 | 147 |
| 7 | 49 |
| 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つずつ選んで掛け合わせます。
| × | 1 | 3 | 9 |
|---|---|---|---|
| 1 | 1 | 3 | 9 |
| 2 | 2 | 6 | 18 |
| 4 | 4 | 12 | 36 |
| 8 | 8 | 24 | 72 |
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 なら次のとおりです。
| 数 | 2 | 3 | 5 |
|---|---|---|---|
| 60 | 22 | 3 | 5 |
| 90 | 2 | 32 | 5 |
| 120 | 23 | 3 | 5 |
| 最大公約数30 | 2 | 3 | 5 |
| 最小公倍数360 | 23 | 32 | 5 |
最大公約数は 2 × 3 × 5 = 30、最小公倍数は 23 × 32 × 5 = 360 です。どれか1つの数にしかない素因数は、最大公約数には入りません。
2. すだれ算で求める
すべての数を割れる素数で割っていき、左に並んだ素数を掛けると最大公約数です。2つの数なら、左の素数といちばん下に残った数をすべて掛けると最小公倍数です。84 と 126 なら、最大公約数は 2 × 3 × 7 = 42、最小公倍数は 2 × 3 × 7 × 2 × 3 = 252 です。
| 2 | 84 | 126 |
| 3 | 42 | 63 |
| 7 | 14 | 21 |
| 2 | 3 |
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以外の公約数を持たなくなったら終わりで、左の素数と、いちばん下の数をすべて掛けると最小公倍数です。
| 2 | 60 | 90 | 120 |
| 3 | 30 | 45 | 60 |
| 5 | 10 | 15 | 20 |
| 2 | 2 | 3 | 4 |
| 1 | 3 | 2 |
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桁) |
|---|---|---|
| √8 | 2√2 | 2.8284 |
| √12 | 2√3 | 3.4641 |
| √18 | 3√2 | 4.2426 |
| √20 | 2√5 | 4.4721 |
| √24 | 2√6 | 4.8990 |
| √27 | 3√3 | 5.1962 |
| √32 | 4√2 | 5.6569 |
| √45 | 3√5 | 6.7082 |
| √48 | 4√3 | 6.9282 |
| √50 | 5√2 | 7.0711 |
| √72 | 6√2 | 8.4853 |
| √75 | 5√3 | 8.6603 |
| √98 | 7√2 | 9.8995 |
| √200 | 10√2 | 14.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 はどの数でも割り切れるので、素因数分解も、約数・倍数の計算もしません。
よくある質問
素因数分解のやり方を教えてください。
1009 は素数ですか? どこまで割ればいいですか?
1 は素数ですか?
60・90・120 の最小公倍数は? すだれ算で720になってしまいます。
3つの数の最大公約数はどう求めますか?
ユークリッドの互除法とは何ですか?
素因数分解から約数を全部出すには? 約数の個数は?
最大公約数と最小公倍数から、2つの数を求めるには?
√72 を簡単にするには?
「最大公約数 × 最小公倍数 = 2つの数の積」は、3つの数でも成り立ちますか?
関連するツール
計算式と出典
- 文部科学省「小学校学習指導要領(平成29年告示)」(PDF)第2章 第3節 算数〔第5学年〕2 内容 A 数と計算 (1) ア(イ)(約数,倍数について知ること)、〔用語・記号〕(最大公約数・最小公倍数・通分・約分)、3 内容の取扱い (1)(最大公約数や最小公倍数を形式的に求めることに偏ることなく,具体的な場面に即して取り扱う)。p.83・87。掲載ページ:文部科学省「平成29・30・31年改訂学習指導要領(本文、解説)」
- 文部科学省「小学校学習指導要領(平成29年告示)解説 算数編」(平成29年7月、PDF)第3章 第5学年 A(1) ア(イ) 約数,倍数(約数・倍数・公約数・最大公約数・公倍数・最小公倍数の意味、8と12の例、0は倍数に含めないこと)p.235、A(4)(約分は分子と分母を公約数で割ること、通分の分母には最小公倍数を用いると簡潔なこと)p.244〜245。掲載ページ:文部科学省「小学校学習指導要領(平成29年告示)解説」
- 文部科学省「中学校学習指導要領(平成29年告示)」(PDF)第2章 第3節 数学〔第1学年〕〔用語・記号〕(自然数・素数)p.67、3 内容の取扱い (1)(自然数を素数の積として表すことを取り扱う)p.69
- 文部科学省「中学校学習指導要領(平成29年告示)解説 数学編」(平成29年7月、PDF)第3章 第1学年 A(1)「自然数を素数の積として表すこと」(1より大きい自然数は素数と素数でない数に分けられること、素因数分解の表し方はただ一通りに決まること)p.67。掲載ページ:文部科学省「中学校学習指導要領(平成29年告示)解説」
- 文部科学省「高等学校学習指導要領(平成30年告示)」(PDF)第2章 第4節 数学 第4 数学A 3 内容の取扱い (4)(内容の(3)「数学と人間の活動」のアでは,整数の約数や倍数,ユークリッドの互除法…についても扱う)p.99
- 文部科学省「高等学校学習指導要領(平成30年告示)解説 数学編 理数編」(平成30年7月、PDF)第1部 第2章 第4節 数学A 3 (3) 数学と人間の活動[内容の取扱い](4)(ユークリッドの互除法が公約量を求めるアルゴリズムであることを理解した上で、2つの整数の公約数を求めること)p.96〜97。掲載ページ:文部科学省「高等学校学習指導要領(平成30年告示)解説」
- J. Sorenson, J. Webster「Strong pseudoprimes to twelve prime bases」Mathematics of Computation, Vol. 86, No. 304, pp. 985–1003(arXiv:1509.00864)定理1.1(最初の12個・13個の素数を底とする強い擬素数の最小値 ψ12 = 318,665,857,834,031,151,167,461、ψ13 = 3,317,044,064,679,887,385,961,981)
素因数分解は、小さい素数から順に割る試し割り(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 など)は読み替えずに知らせます。