約数計算
計算結果
約数
- 約数の組
- 1 * 60, 2 * 30, 3 * 20, 4 * 15, 5 * 12, 6 * 10
整数の約数とは、その数を余りなく割り切るもう1つの整数のことです。60の約数は1、2、3、4、5、6、10、12、15、20、30、60の12個で、それらはいつも掛けると60に戻る組になります。1と60、2と30、3と20、4と15、5と12、6と10です。このページは約数の一覧と約数の組の両方を印字します。問いが違うからです。一覧はある数が別の数を割り切るかどうかを確かめたいときに要るもので、組はその面積の長方形を探したいとき、あるいは積が決まっている2つの数を探したいときに要るものです。方法は試し割りで、役に立つのはどこで止めるかを知っていることです。60の約数をすべて見つけるのに、7より大きい数を試す必要はありません。8 × 8 = 64が60を超えているからです。平方根を超えると、見つかる約数はすべて、すでに出会った小さいほうの半分を持つ組の大きいほうになります。だから60は59回ではなく7回の試行で済み、このページの上限が100万でも7桁の数が速いままなのです。同じ打ち切りが組を昇順に並べます。小さい約数が見つかるたびに、その相棒が同じ瞬間に作られるので、組は並べ替えの段を挟まずに小さいほうの順にそろいます。出力を読む前に知っておく価値のある特別な場合が2つあります。素数は約数をちょうど2つ、つまり1とその数自身だけ持つので、約数の一覧は短く、組の一覧は1件です。平方数は約数の個数が奇数になります。真ん中の組が同じ数の2つ組だからです。36は約数を9個持ち、組は6 * 6で終わります。このページはそれを1回だけ印字します。どちらもエラーではなく、コードの中でも特別扱いではありません。同じループから出てきます。このページがしないのは、数を素数の積に分解することです。約数をすべて、組をすべて示しますが、60 = 2² × 3 × 5とは決して言いません。約数の一覧にはその材料が入っていますが、それは素因数分解ではありません。この区別は数が大きいときに効いてきます。このページの手間は入力の平方根で増えるのに対し、素因数分解は本当に難しく、2つは別の問いだからです。
3つの数の約数と約数の組を並べたもの
| 数 | 約数 | 約数の組 |
|---|---|---|
| 12 | 1, 2, 3, 4, 6, 12 | 1 * 12, 2 * 6, 3 * 4 |
| 36 | 1, 2, 3, 4, 6, 9, 12, 18, 36 | 1 * 36, 2 * 18, 3 * 12, 4 * 9, 6 * 6 |
| 60 | 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60 | 1 * 60, 2 * 30, 3 * 20, 4 * 15, 5 * 12, 6 * 10 |
行を横に読むと、真ん中の列が3列目を開いたものになっています。12は約数が6個で組が3つ、36は約数が9個で組が5つ、60は約数が12個で組が6つです。比べるべきは個数のほうです。6は偶数、9は奇数、12は偶数で、表の中で平方数なのは36だけです。36だけが仲間外れなのはまさにそのためです。平方根以外の約数には組になる相手がいるので、偶数個を稼ぎます。平方根だけが自分自身しか持ちません。もう1つ見ておく価値があるのは、数が大きいほど約数が多くなるわけではないことです。36は12の3倍で約数は1.5倍、60は12の5倍で約数は2倍です。約数がいくつあるかは素数の部品の組み合わせ方で決まり、数そのものの大きさでは決まりません。100万よりずっと小さい720,720が、そのあたりのどの数よりも約数が多いのも同じ理由です。
公式
60 ÷ 1 = 60 ⇒ 1 * 60、60 ÷ 2 = 30 ⇒ 2 * 30、60 ÷ 3 = 20 ⇒ 3 * 20、60 ÷ 4 = 15 ⇒ 4 * 15、60 ÷ 5 = 12 ⇒ 5 * 12、60 ÷ 6 = 10 ⇒ 6 * 10、60 ÷ 7は割り切れず、8 × 8 > 60なので終了
- n
- 約数を調べる数で、1から1,000,000までの整数です。1も許され、約数を1つだけ返します。これは退化した答えではなくれっきとした答えです。1は自分自身の約数だからです
- d
- 試し割りに使う約数で、1、2、3、4…と順に試します。このページはnの平方根より先を試しません。その打ち切りがこの方法の肝です。d × e = nでdが平方根より大きいなら、eは平方根より小さいので、eはすでに見つかっていて組もすでに印字されています
- d * d ≤ n
- 打ち切り規則を書き下したものです。60では最後に試す約数が7になります。7 × 7 = 49は60より小さく、8 × 8 = 64は60を超えるからです。この規則のおかげで試行回数は入力そのものではなく入力の平方根で増えます。1,000,000でも試行は1,000回で、1,000,000回ではありません
- n / d
- 約数の相棒です。dがnをちょうど割り切るとき、商が組のもう半分で、このページはそれを同じ段で作ります。60の組が1 * 60、2 * 30、3 * 20…と順に出てくるのはそのためで、並べ替えは要りません。小さいほうの半分が昇順に見つかるので、組も昇順になります
- 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60
- 60の約数を1本の一覧にしたもので、昇順です。12個と偶数なので、組がすべてそろっています。約数には必ず相棒がいます。この一覧は下の組と同じ情報を並べ直したものです。組を読んで数を集めれば、この行に戻ります
- 6 * 6
- 36の真ん中の組で、同じ数が1行に2回出てくる唯一の形です。36は平方数なので約数の個数が奇数になります。1、2、3、4、6、9、12、18、36の9個で、このページは真ん中の組を2回ではなく1回だけ印字します。平方数の約数の個数が偶数にならないのはそのためです
約分が、約数の一覧を求めるときのいちばんよくある理由です。42/60を手で約分するには両方を割り切る数を探します。60の約数が候補を教え、42の約数がそのうちどれが使えるかを教えます。そのいちばん大きい数が最大公約数で、それだけが要るなら最大公約数計算がその問いに直接答えます。2つ目は面積が決まった長方形です。60平方メートルの花壇は1×60、2×30、3×20、4×15、5×12、6×10のどれかになり、約数の組はまさにその形の候補の一覧です。組がその形で印字されるのはそのためです。同じ問いは、物を同じ数の行と列に並べるときにも現れます。60人の客を同じ大きさの卓に分ける、クラスを同じ人数の班に分けて余りを出さない、といった場面です。3つ目は主張の検算です。91は素数だと言われたら、約数の一覧が決着をつけます。1、7、13、91で、件数が2ではなく4になることが反証です。2、3、5、9の割り切れる規則は小さい場合は手で足りますが、このページはそれが面倒になったところから引き受けます。問いが約数ではなく部品そのものについてのときは、答えは別の場所にあります。素因数分解計算はこのページが意図的にしないことをして数を素数に分け、最小公倍数計算と最大公約数計算は1つの数を説明するのではなく2つの数を比べ、約分の計算は一覧を見せずに公約数で分数を直接簡単にします。
計算例
約数が12個：60
- 1を試す：60 ÷ 1 = 60でちょうど割り切れるので、1と60はどちらも約数
- 2を試す：60 ÷ 2 = 30で2と30が約数。3を試す：60 ÷ 3 = 20で3と20
- 4を試す：60 ÷ 4 = 15で4と15。5を試す：60 ÷ 5 = 12で5と12
- 6を試す：60 ÷ 6 = 10で6と10。7を試す：60 ÷ 7は整数にならない
- 8 × 8 = 64は60を超えるので終了。12個の約数がそろった
初期値で、60は約数が多いので良い初期値です。12個は、それより小さいどの数よりも多い個数です。探索の安さにも注目してください。試した約数は7つで、60ではありません。組の行と約数の一覧は同じ12個の数です。組は、それぞれが掛け合わされる相手の隣に来るように折りたたんだだけです。組の一覧が6 * 10で終わり、10 * 6に続かないことにも意味があります。組の小さいほうが平方根を超えたら、残りの組はすべてすでに印字したものの繰り返しです。
平方数：36
- 1と36、次に2と18、次に3と12、次に4と9が組になる
- 6 × 6 = 36なので、6は自分自身が相棒で、一覧の真ん中に来る
- 7は36を割り切らない。7 × 7 = 49はすでに36を超えているが、平方根より小さい最後の約数は6だった
- 約数は1、2、3、4、6、9、12、18、36の9個で、奇数個
約数の個数が奇数になりうる理由が分かる場合です。平方根以外の約数にはそれぞれ別の相棒がいて、2個ずつ数に足します。平方根だけが自分自身と組になり、1個足します。36の約数が9個で、それより大きい60が12個、12が6個なのは、それだけの理由です。組の行が6 * 6を2回ではなく1回だけ印字するのは選択です。2回印字すると、2つの行が約数の個数について食い違ってしまいます。
素数：7
- 1を試す：7 ÷ 1 = 7でちょうど割り切れるので、1と7が約数
- 2を試す：7 ÷ 2は整数にならない。3 × 3 = 9は7を超えるのでここで終了
- 1と7の間に7を割り切る数はない
- 約数が2個、組が1つ。これが素数の定義
このページで最も短い非自明な出力で、素数は分解できなかったのではないことが分かります。素数とは約数をちょうど2つ持つ数で、その2つはいつも1とその数自身です。このページは見つけられなかったとは報告せず、そうなっていると報告します。打ち切り規則がここでは実際に働いています。2を試した後にはもう試すものがありません。3 × 3がすでに7より大きいからです。3、4、5、6を試すと割り算が4回増えますが、何も見つかりません。
適用限界
入力は1から1,000,000までの整数でなければなりません。0は拒否します。どんな整数も0を割り切るので、約数の一覧は無限になり、印字できるものがありません。負の数も拒否します。±1、±2…はどれも−60を割り切りますが、このページが報告するのは正の数の正の約数であって、両方の符号を出すかどうかの取り決めが要る形は、ここでは明記していません。小数は丸めずに拒否します。上限の1,000,000が試し割りを有限に保ちます。探索は平方根で止まるので、最悪でも試行は1,000回で、答えの一覧は長くなっても手に負えない長さにはなりません。それでも長くはなります。720,720は約数を240個持ち、100万未満のどの数よりも多い個数です。その大きさの一覧は正しいのですが、読むのは楽しくありません。このページが報告するのは約数と約数の組で、素因数ではありません。違いは見落としやすいものです。60の約数の一覧には2、3、5が入っていますが、このページは60 = 2² × 3 × 5とは決して言いません。大きな数ではこの2つの問いの費用はまったく違います。2、3、5、9の割り切れる規則は別立てでは出てきません。試し割りに吸収されているだけなので、末尾が0の数は2、5、10を約数として示しますが、理由には触れません。約数はすべてコンマ区切りの整数として印字され、組は掛け算にアスタリスクを使います。桁区切りは使わないので、100万の約数は「1000000」と印字されます。最後に、下の参考表は3つの固定した数を示すもので、入力には追随しません。入力した数に答えるのは上のパネルです。
よくある質問
- 約数と数えられるのはどこまでか
- その数を余りなく割り切る整数すべてです。組の両方が数えられます。60なら一覧は1から60まで続き、1とその数自身はいつも約数で、面白いのはその間の数です。ちょうど割り切れる場合でも分数は数えません。2.5は60の中に24回入りますが、2.5は整数ではないので約数ではありません。このページは正の数の正の約数を並べるという標準的な取り決めに従います。
- なぜ探索は平方根で止まるのか
- それを超えると、見つかる約数はすべて、すでに見たものの相棒になるからです。d × e = 60でdが60の平方根より大きいなら、eは平方根より小さいので、eはもっと前に試されていて、そのとき組が印字されています。その先を試しても、組を逆の順でもう一度見つけるだけです。60が60回ではなく7回の試行で済む理由がこれで、このページの費用が入力の平方根で増える理由でもあります。100万に近い数でも試行は1,000回ほどで、100万回ではありません。
- 36の約数の個数が奇数なのはなぜか
- 36が平方数で、その平方根が自分自身と組になるからです。それ以外の約数にはそれぞれ別の相棒がいて、1と36、2と18、3と12、4と9のように、組ごとに個数を2つ増やします。そこに6 × 6 = 36が1つ足されます。合計は4 × 2 + 1 = 9です。一般に、約数の個数が奇数になるのはその数が平方数であるときに限り、約数の一覧を見て平方数かどうかを見分けるいちばん速い方法がこれです。
- 素因数分解と同じものか
- 違います。違いははっきりさせておく価値があります。このページが返すのは約数すべてで、素因数分解は数を素数だけの積に分けます。60の素因数分解は2² × 3 × 5ですが、このページはそれを印字しません。ただし2、3、5はどれも約数の一覧に現れます。素数もほかの数と同じように約数だからです。実用上の違いは費用です。このページの手間は数の平方根に比例し、素因数分解は大きな数では本当に難しくなります。公開鍵暗号がそこに乗っているのは、その難しさのおかげです。
- 0や負の数は入力できるのか
- できません。どちらも勝手な制限ではありません。どんな整数も0を割り切るので、約数の一覧は終わりません。負の数では約数が両方の符号に現れ、1と−1、2と−2…のようになります。両方を並べるかどうかの立場をこのページは決めていません。入力は1から1,000,000までの整数です。小数も丸めずに拒否します。丸めると、別の数についての問いに黙って答えてしまうからです。
- 約数が2つの列に分かれているのはなぜか
- 2つの別の問いに答えるからです。平らな一覧は、ある数が自分の数を割り切るかどうかを確かめるときに見るものです。組は、選んでいる2つのものの積として数を見るときに要るものです。その面積の長方形、同じ数の行と列、余りを出さない班分けなどです。60平方メートルの花壇は1×60、2×30、3×20、4×15、5×12、6×10のどれかになり、その6つの形が組の列そのものです。2つの列は同じ数を持っていて、並び方だけが違います。
参考文献
- Divisor — ある整数が別の整数を余りなく割り切るとはどういうことか、そしてどの数も自分自身を割り切るという取り決め — Wolfram MathWorld (United States)
- Prime Number — 約数をちょうど2つ持つ数と、その定義が約数の一覧で目に見える理由 — Wolfram MathWorld (United States)
- Perfect Square — 平方根が整数になる数と、その約数の個数がいつも奇数になる理由 — Wolfram MathWorld (United States)
- 学習指導要領（平成29・30・31年改訂） — 算数・数学の「数と計算」領域における約数と倍数の扱いと、約数の組を並べて考える学習活動の根拠になる文部科学省の告示・解説 — 文部科学省