素因数分解計算

360 = 2^3 * 3^2 * 5、Omega(360) = 3 + 2 + 1 = 6、d(360) = (3+1) * (2+1) * (1+1) = 24

n

分解される数で、1から1,000,000までの整数です。この範囲は数論モジュールが全体で使っているもので、約数のページとぴったり同じなので、行き来する読者は同じ境界に出会います。小数は丸めずに拒否し、0と負の数も拒否します。素因数分解は正の整数についての主張だからです

p

素因数、つまりnをちょうど割り切る素数のことです。小さい順に試し割りして見つけるので、いちばん小さい素数がいつも先に取り出され、印字される分解は必ず小さい素数から大きい素数へ並びます。360なら素数は2、3、5で、ほかの素数はどれも360を割り切りません

e

素数に付く指数で、その素数が積の中に何回現れるかです。360は2 × 2 × 2 × 3 × 3 × 5なので、2は3回、3は2回現れます。1回しか現れない素数には指数をまったく付けません。360の中の5は5^1ではなく素の5として書きます。これが通例で、短い分解を読みやすく保ちます

2^3 * 3^2 * 5

印字されたままの360の分解で、既定の入力でもあります。山形記号が指数、アスタリスクが掛け算を表すので、そのまま平文の入力欄や検索窓に貼り付けても壊れません。1より大きい整数それぞれについてこの表記はちょうど1つしかなく、だからこそ印字する価値があります。360は別の素数の積としても書ける、ということはありません

Omega(360) = 3 + 2 + 1 = 6

重複を込めて数えた素因数の個数です。2が3つ、3が2つ、5が1つで合わせて6つになります。人が驚くほうの数で、360は3つの素数からできているように感じられるからです。数え方は指数を足すことで、異なる素数の個数を数えるのではありません。指数が1より大きい素数があるたびに、2つの答えは食い違います

d(360) = (3+1) * (2+1) * (1+1) = 24

正の約数の個数で、同じ指数から、それぞれに1を足して掛け合わせて求めます。並べると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個です。これは上の個数とは別の問いへの答えで、360を作る素数ではなく360を割り切る数を数えています

分解が欲しくなるのは、問いが数の大きさではなく掛け算の構造についてのときです。分数や平方根の整理が日常的な例です。72の平方根は72 = 2³ × 3²なので6√2になり、各素数の指数が根号の外へ何個出せるかを教えてくれます。これは平方根のページが読んでいるのと同じ分解です。2つの数の最大公約数や最小公倍数を求めるのも同じことで、数を1つずつ分解します。共通の素数を小さいほうの指数で取れば最大公約数、すべての素数を大きいほうの指数で取れば最小公倍数です。割り切れるかどうかの問いも同じように答えます。ある数が別の数を割り切るのは、その素数と指数が相手の中にすべてそろっているときちょうどです。数論では、分解が決めるのはその数が素数かどうか、約数がいくつあるか、平方数かどうか（指数がすべて偶数）、立方数かどうかです。この方法の限界も知っておく価値があります。試し割りは100万なら速く、100桁の数ならお手上げです。この易しさと難しさの隔たりこそ、公開鍵暗号がその上に築かれているものです。あなたの数を割る数がどれかという問いなら約数のページが並べ、その数がそもそも素数かという問いなら素数のページが直接答えます。

1. 既定の入力：360

   1. 360は偶数なので2で割ります。360 / 2 = 180、180 / 2 = 90、90 / 2 = 45で、都合3回です
   2. 45は偶数ではありません。次の素数は3で、45 / 3 = 15、15 / 3 = 5と、2回です
   3. 5は素数なので、分解は2 × 2 × 2 × 3 × 3 × 5、つまり2^3 * 3^2 * 5です
   4. 素因数を重複込みで数えます。3 + 2 + 1 = 6です
   5. 約数を指数から数えます。(3 + 1) × (2 + 1) × (1 + 1) = 4 × 3 × 2 = 24です

   既定の入力であり、2つの個数をなぜ並べて印字するのかを見せる例です。6と24が隣り合っていて、両方一致するはずだと思った読者はどちらかが壊れていると考えるでしょう。そうではありません。6は繰り返しを全部残したときにその数が何個の素数の部品からできているかで、24はその数を割り切る数が何個あるかです。両者の隔たりは指数から来ます。素数の繰り返しはどれも、部品の個数をほとんど増やさずに約数の個数を掛け算で増やします。どちらか一方を手で確かめれば計算は短く、両方を確かめればどちらがどちらか忘れなくなります。

2. 隔たりが見える小さい例：12

   1. 12 / 2 = 6、6 / 2 = 3なので、2は2回現れます
   2. 3は素数なので、分解は2^2 * 3です
   3. 素因数を重複込みで数えます。2 + 1 = 3で、これは2と2と3です
   4. 約数を並べると1、2、3、4、6、12で、6個あります
   5. 配方で確かめます。(2 + 1) × (1 + 1) = 3 × 2 = 6で、一覧と一致します

   このページが扱っている混同の、いちばん分かりやすい小さい例です。どちらの個数も数秒で手で確かめられる大きさだからです。12は3つの素数（2、2、3）からできていて、6つの数が12を割り切ります。出力を「約数が3個」「素因数が6個」と読むのはどちらもそれらしく聞こえ、どちらも間違いです。約数の一覧は6が偶数個になる組分けも見せます。1と12、2と6、3と4です。12は平方数ではないので、自分自身と組になる約数はなく、だから個数が偶数になります。

3. 厄介な場合：1

   1. 1はどの素数でも割り切れません。2でも3でも5でも、割れば分数が残ります
   2. したがって素因数はなく、その個数は0です
   3. 1を割り切る正の数は1自身だけなので、約数の個数は1です
   4. 分解は、空欄ではなく1桁の1として印字されます

   導出するのではなく決めなければならない場合で、その決定は1を印字することです。分解を空欄にすると計算に失敗したように読めます。結果欄が絶対に見えてはいけない姿がそれです。すると2つの個数は正直に出てきます。素数は1つもなく、約数は1つです。1は素数でも合成数でもなく、掛けても何も変わらない乗法の単位元であり、このページはそうでないふりをしません。拒否せずに受け入れるのは入力範囲が1から始まるからで、自分の範囲の下端を除外する範囲のほうが説明に困ります。

入力は1から1,000,000までの整数でなければなりません。0は拒否します。どの素数も0を割り切るので、積が無限になってしまうからです。負の数も似た理由で拒否します。素数はやはりそれを割り切りますが、符号を別に持ち運ばなければならず、一意分解の主張は正の数についてのものだからです。小数は丸めずに拒否します。丸めれば黙って別の数についての問いに答えることになるからです。上限の100万は数論モジュール共通のもので、正しさではなく費用の問題です。平方根までの素数で試し割りするのは、100万なら速く、20桁の数なら絶望的です。これはこの方法の本物の境界で、公開鍵暗号が成り立っているのも同じ境界です。このページが報告するのは分解と2つの個数だけで、それ以外は何もありません。約数そのものを並べることはせず、複数の数の最大公約数や最小公倍数も計算せず、根号や分数の整理もしません。指数1は決して印字しないので、1回だけ現れる素数は裸の数として出ます。掛け算の記号は全体を通してアスタリスクで、つまり出力は千位の区切りを持たない平文のASCIIです。最後に、下の参考表は入力に追随せず4つの固定された数を示します。

このページの2つの個数は何が違いますか

1つ目は素因数を重複も込めて数えたもので、2つ目は約数を数えたものです。12なら答えは3と6で、どちらも正しいのです。12は2 × 2 × 3なので3つの素数の部品からできており、1、2、3、4、6、12がどれも12を割り切るので約数は6つです。小さい入力では2つの数が近いので混同は自然です。1つ目の求め方は指数を足すことで、2つ目の求め方は各指数に1を足して掛けることです。この掛け算のせいで2つ目はるかに速く走り去ります。素数の繰り返しが1回ごとに約数の個数を掛け算で増やし、1つ目には1しか足さないからです

素因数分解は1通りしかありませんか

はい、そしてそれは約束ごとではなく定理です。1より大きい整数はどれも素数の積として書け、順序を無視すればその書き方はちょうど1通りです。360はいつでも2³ × 3² × 5でしかなく、別の素数の積でもあるということはありません。この結果は算術の基本定理と呼ばれ、これがなければ分解を印字するのは答えではなく珍品になります。このページがいちばん小さい素数を先に印字し、それが正規の形だと確信できるのも同じ理由です。順序は読みやすさのために選んだもので、固定して失われるものは何もありません

1はどう扱われますか

分解として1を印字し、素因数は0個、約数は1個です。1は素数でも合成数でもありません。通常の意味での素因数分解を持たず、上の定理が1より大きい数について述べられているのはそのためです。しかし結果欄が空だと計算に失敗したように読めるので、このページはその桁を印字し、2つの個数を正直に報告します。1の約数の個数は本当に1で、1を割り切る正の数は1自身だけです。素因数の個数も本当に0です。拒否せずに受け入れるのは入力範囲が1から始まるからで、自分の範囲の下端を拒否するほうが説明に手間がかかります

なぜ100万で止まるのですか

方法が試し割りで、その費用が数の平方根とともに増えるからです。100万に近い数の素因数を探すには1,000までの約数を試すことになり、一瞬です。20桁の数なら100億まで試すことになり、そうはいきません。この隔たりは実装の細部ではなく問題そのものの性質で、公開鍵暗号がその上に築かれている前提です。大きな数の分解が難しいことが、通信を秘密に保っています。100万の範囲ならどれも即座に返り、上限はタイムアウトに隠されず入力に明記されています

因数の一覧より分解が欲しいのはどんなときですか

問いが所属ではなく構造についてのときです。72の平方根を整理するには72 = 2³ × 3²が必要です。指数が、各素数を根号の外へ何個出せるかを教えてくれるからで、答えは6√2になります。2つの数の最大公約数を求めるには両方の分解が要ります。答えが共通の素数を小さいほうの指数で取ったものだからです。平方数かどうかの判定は指数を一目見るだけです。すべて偶数なら平方数です。約数を並べるのは別の問いで、数によってはずっと長い答えになります。720,720は約数を240個持ち、印字するには多く、眺めるには少ない量です。それが欲しいときは約数のページが並べます

素数が1回だけのとき指数が印字されないのはなぜですか

5が1つのときに5^1と書くのは雑音だからです。数学の通例では指数は1より大きいときだけ印字するので、360は2^3 * 3^2 * 5となり最後の項は裸になります。落としても失われるものはありません。指数がなければ指数は1、と曖昧さなく決まります。すべてが1回ずつの素数でできた数（無平方数のことです）は、山形記号のないただの積として読めます。97が素数で、97^1ではなくただの97として印字されるのも同じ通例です

• Prime Factorization — 整数を素数の積として書くことと、その素数を見つける算法 — Wolfram MathWorld (United States)
• Fundamental Theorem of Arithmetic — 1より大きい整数はどれも素因数分解をちょうど1つ持つという定理。それを印字する価値の根拠 — Wolfram MathWorld (United States)
• Divisor Function — 正の約数の個数、指数からそれを組み立てる式、単一素数の冪での振る舞い — Wolfram MathWorld (United States)
• 学習指導要領（平成29・30・31年改訂） — 分解質因数と約数・倍数が小学校高学年の「数と計算」領域で扱われることを示す文部科学省の告示・解説 — 文部科学省