素因数分解のやり方

素因数分解とは、2以上の整数を、それ以上分解できない素数のかけ算だけで表すことです。例えば12は2×2×3、360は2×2×2×3×3×5に分解できます。分数を約分するときの共通因数を見つけたり、ある数のすべての約数を洗い出したり、暗号のように大きな数の性質そのものを扱ったりする場面で、素因数分解は避けて通れない基本操作です。

手計算での試し割り

手で素因数分解をする方法はいたってシンプルで、試し割りと呼ばれます。小さい素数から順に、割り切れなくなるまで割り続けるだけです。360を例に、実際にやってみます。

360は偶数なので、まず2で割ります。360÷2=180。180もまだ偶数なので、もう一度2で割ります。180÷2=90。90も偶数なので、さらに2で割ります。90÷2=45。45は奇数になったので、2で割るのはここで終わりです。ここまでで2が3回出てきました。

次は3を試します。45÷3=15。15もまだ3で割り切れます。15÷3=5。5は3で割り切れないので、3で割るのはここで終わりです。3が2回出てきました。

残った5はそれ自体が素数なので、5÷5=1でちょうど割り切れて終わります。

手順を表にまとめると次のようになります。

割る数	計算	商
2	360÷2	180
2	180÷2	90
2	90÷2	45
3	45÷3	15
3	15÷3	5
5	5÷5	1

出てきた素因数を数え上げると、2が3回、3が2回、5が1回です。指数の形でまとめると、360=2³×3²×5となります。検算すると、2³=8、3²=9、8×9=72、72×5=360で、確かに元の数に戻ります。

もっと大きい例と素数判定

数が大きくなると、闇雲に割り続けるのは非効率です。ここで効いてくるのが、試している除数の2乗が残った数を超えたら、それ以上割れる数はなく、残りはそれ自体が素数だという性質です。

997が素数かどうか調べてみます。997の平方根はおよそ31.6なので、31以下の素数、つまり2、3、5、7、11、13、17、19、23、29、31だけを試せば十分です。997は奇数なので2では割れません。桁の和は9+9+7=25で3の倍数ではないので3でも割れません。末尾が0でも5でもないので5でも割れません。7で割ると997÷7=142余り3、11で割ると997÷11=90余り7、13で割ると997÷13=76余り9、17で割ると997÷17=58余り11、19で割ると997÷19=52余り9、23で割ると997÷23=43余り8、29で割ると997÷29=34余り11、31で割ると997÷31=32余り5。どれで割っても余りが出ました。次に試すべき素数は37ですが、37²=1369はすでに997を超えているので、これ以上試す必要はありません。997は素数です。

似たような桁数の1001を試すと様子が違います。1001は奇数で、3でも5でも割れませんが、7で割ると1001÷7=143で割り切れます。143はさらに11×13に分解できるので、1001=7×11×13です。見た目の桁数がほぼ同じでも、997は素数、1001は3つの素数の積という、まったく違う性質を持っています。

いくつかの数について、素因数分解と素数かどうかを一覧にすると次のようになります。

数	素因数分解	素数か
17	17	はい
45	3²×5	いいえ
97	97	はい
360	2³×3²×5	いいえ
997	997	はい
1001	7×11×13	いいえ

自分の数字で計算してみる

自分で試し割りを繰り返すのは、数が大きくなるほど手間がかかります。実際にどんな数字で試してみたいときは、下のツールに入力すればすぐに素因数分解の結果を確認できます。

素因数分解の計算ツール

無料、登録不要、どの端末でも使えます。

フルツールを開く

実用例

分数を素因数分解で約分する

分数の約分は、分子と分母を素因数分解して共通の因数を取り除くと確実にできます。84/126という分数を例にします。

84を素因数分解すると2²×3×7、126を素因数分解すると2×3²×7です。両方に共通して現れる素因数を、指数の低い方だけ拾うと、2は両方にあり指数の低い方は2¹、3は両方にあり指数の低い方は3¹、7は両方にあり指数は1同士なので7¹です。共通因数は2×3×7=42になります。

分子と分母をそれぞれ42で割ると、84÷42=2、126÷42=3なので、84/126=2/3まで約分できます。ユークリッドの互除法で最大公約数を求めても同じ42という答えにたどり着きますが、素因数分解を使うと、なぜその数が共通因数になるのか、途中経過が目に見える形で確認できるという利点があります。

すべての約数を洗い出す

360の約数をひとつずつ書き出そうとすると、どこまで探せば全部見つかったと言えるのか分かりにくくなります。素因数分解を使えば、約数の総数を計算だけで求められます。

360=2³×3²×5なので、それぞれの指数に1を足して掛け合わせます。(3+1)×(2+1)×(1+1)=4×3×2=24です。360には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と数えると、確かに24個です。書き出したあとで数が合わなければ、素因数の組み合わせのどこかを見落としている、という確認にも使えます。

大きな数の素因数分解が難しいという性質は、もっと大きなスケールでも役に立っています。RSA暗号のような公開鍵暗号方式は、大きな2つの素数を掛け合わせるのは一瞬でできるのに、その積から元の2つの素数を逆算するのは(桁数が十分大きければ)現実的な時間では終わらないという非対称性を安全性の根拠にしています。

よくある間違いと境界ケース

0と1は、素数でも合成数でもありません。素数の定義は「1と自分自身以外に約数を持たない、1より大きい整数」なので、1はこの定義の対象外です。0はすべての整数で割り切れてしまうため、素因数分解という考え方そのものが成り立ちません。

負の数を素因数分解したいときは、絶対値に置き換えてから計算します。マイナス60を素因数分解したいなら、60=2²×3×5で計算し、符号は別に扱います。

試し割りをいつまで続ければいいのか迷う人は多いですが、目安は単純です。試している除数の2乗が、残っている数を超えたら、それ以上割れる数はなく、残りの数はそれ自体が素数です。997の例で31の次の素数である37を試さなかったのは、37²=1369が997を超えていたからです。この目安を知らないと、大きな数を素数かどうか確かめるときに、必要のない割り算を延々と続けることになります。

もう一つの見落としやすい点は、同じ素因数を重複して数え忘れることです。360を2で割れるだけ割ると3回出てきますが、割り切れなくなる前に次の素数に進んでしまうと、指数がずれてしまい、掛け合わせても元の数に戻りません。割り切れなくなるまで同じ素数で割り続けてから次の素数に移る、という順番を飛ばさないことが重要です。

よくある質問

素因数分解は何に使うのですか。 分数の約分、ある数のすべての約数を求める計算、複数の数の最大公約数や最小公倍数を求める計算の土台になります。暗号の分野でも、大きな数を素因数分解するのが計算上非常に困難であるという性質が、RSA暗号のような公開鍵暗号方式の安全性の根拠として使われています。

見ただけで素数かどうか分かる方法はありますか。 完全に見ただけで判定できる方法はありませんが、除外できるケースはいくつかあります。偶数(2以外)は素数ではありません。末尾が0または5の数(5以外)は素数ではありません。各桁の和が3の倍数になる数は素数ではありません。これらに当てはまらなければ、試し割りで確認する必要があります。

手計算で現実的に扱える最大の数はどれくらいですか。 4桁から5桁くらいまでなら、試し割りで十分現実的に手計算できます。997のように平方根が31程度の数でも、試す素数は11個で済みました。ただしこれが6桁、7桁と伸びていくと、試すべき素数の数も増え、手作業では時間がかかりすぎます。その場合は計算ツールに任せるのが現実的です。

素因数分解の結果は、書く順番を変えても同じ答えになりますか。 はい。ある整数の素因数分解は、並び順を除けばただ一通りに定まります。これは算術の基本定理と呼ばれる性質で、360を2³×3²×5と書いても3²×2³×5と書いても、同じ分解を表しています。慣習として、小さい素数から大きい順に並べるのが一般的です。