2005.02.20
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
ＭＲＭ [ MOTOMACHI RADIO MAIL ] Vol.006
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
......................................................................
SUMMARY
- 不定期連載「それがどうした」 [4] 約数のはなし・前編
- 元町二十四軒 ：検索家
-おしらせ
----------------------------------------------------------------------
不定期連載「それがどうした」
----------------------------------------------------------------------
[4] 約数のはなし・前編
元町二十四軒：検索家
-- 「約数のはなし」の概要 --------------------------------------------
今回は算数系の話題です。「算数の話は好きでない」という機械のような精
神の方には退屈かもしれません。今回のゴールは「1000以下の数で約数が最も
多いものは何か？」という問題を効率良く解く方法を説明することにあります。
数字は整数しかでてこないし、計算も＋×÷がほとんどですので、計算の苦手
な人にもお読みいただける内容になっている筈です。なお、今回は話が長くな
るので前編・後編に分けて、前編では「素数の求め方、累乗、素因数分解」に
ついてお話します。これらの項目について説明の必要の無い方には退屈な内容
だと思いますので後編からどうぞ。
-- 約数の前に素数の話です --------------------------------------------
素数とは「１とその数自信以外の約数を持たない正の整数」の事を言います。
「約数を２つだけ持つ正の整数」と言い換えても良いでしょう。「正の整数」
の辺りが少々冗長ですがご容赦ください。例えば、６の約数は「１，２，３，
６」と４つあるので６は素数ではありません。７の約数は「１，７」と２つし
かないので７は素数です（すみません。怒ってませんか？）。以下、話を簡単
にするために約数という言葉を「１とその数自身」という自明な物を除いた意
味で使います。例えば「約数を求める」は「（１とその数自信以外の）約数を
求める」という意味です。
以下、「エラトステネスのふるい」が何であるかをご存じの方は読み飛ばし
て構いません。
ある数が素数であるかどうかを判定する方法は、実際の所「約数があるか／
ないか」を判定するしかありません。とは言え、例えば 5609 という数が素数
かどうかを判定するために、5609÷2, 5609÷3, … , 5609÷5608 を全て律儀
に試している訳ではなく、もう少し効率を考えた方法を使っています。
・第一に素数以外の数で割り算をする必要はありません。例えば、ある数が３
で割れないことが解っている場合は、６でも９でも割れないのは明らかです。
・次に判定する数の平方根（*1）を越えた数で割り算をする必要もありません。
これは少し説明が必要かもしれません。先程の例で言えば、5609 を割るこ
とをできる数を小さい素数から順に探し、ある数 x で初めて割り切れたと
します。このとき、5609 を x で割った答え y は、x より小さくなること
はありません（x より小さい数はもう試したので）。よって 5609÷x の答
えが x より小さくなった時点でそこから先は探しても見つかりません。こ
の分岐点となるのが、判定する数の平方根です。例えば、5609 の平方根は
74.8…です。つまり、5609 = 74.8…×74.8…な訳ですから、5609 を 74 で
割ったときの答えは 74 より大きく、75 で割ったときの答えは 75 より小
さくなります。
*1 平方根（√）もざっくりと説明しておきましょう。○×○＝□（○は
同じ数）となる場合、「□の平方根は○である」と言います。負の数もあ
るので細かい事を言えば「○は□の平方根（のひとつ）である」なのです
が、とりあえず考えないことにしましょう。解りやすい例で言えば、４の
平方根は２、９の平方根は３です。本稿は整数しか出てきませんので、例
えば「２０の平方根は？」という場合は、４×４＝１６，５×５＝２５
なので、４と５の間だなということさえ解ればOKです。
以上２点を考えると「ある数が素数であるのは、その数の平方根以下の素数
の中にその数を割り切る物が１つも存在しない場合である」と言うことができ
ます。
ここで「『その数の平方根以下の素数』はどうやってそれが素数であること
が解るのか？」という疑問を持った方もいらっしゃると思います。良い数学感
覚をお持ちです。素数であることを判定するために、別の素数を使うと言って
る訳ですから一見この方法は無意味に見えます。ではどうすれば良いか？答え
はもの凄く単純です。同じ方法を使って判定すれば良いのです。「それじゃあ
いつまで経っても終わらないよ」と思う方もいらっしゃると思います。ごもっ
ともな疑問だと思いますが、判定対象となる数を割る数は判定対象と比較して
かなり小さいという事に注目してください。割る数が素数かどうかを判定する
ために同じ方法を使ったとしても、今度は遙かに少ない試行で判定が可能です。
加えて小さい数から順に判定をしているため、割る数が素数であるかどうかを
判定するために必要な素数は全て揃っているという点も考慮すると、判定の連
鎖が無限に続く訳では無いと言うことがお解り頂けるかと思います。以下、具
体例を挙げて説明します。實は、この方法は後で説明する「エラトステネスの
ふるい」に比べるとあまり効率が良いやり方では無いのですが、考え方を説明
するために一度通過しておく事にします。
5609が素数であるかどうかを判定する手順：
0.ゴールの確認：5609の平方根は74.89なので、これより小さい素数で5609を
割ることが出来るものが一個でも見つかれば、5609は素数ではない。
1.小さい数から順に試す。まず2で割り切れないことはすぐ解るので、以下奇
数についてのみ試すことにする。また、割る数が素数であるかどうかを判定
するために、これまで見つかった素数の一覧を書き留めることにする。
2.判定は省略するが 3 は素数。素数一覧に 3 を書き入れる。5609 は 3 で割
り切れないので、次の奇数 5 について検討する。5が素数であることを判定
するには先程の理由により2で割り切れないことを示せば充分（5の平方根が
2.2…なので）。試すまでもなく割り切れないので 5 は素数であることが
解った。素数一覧に 5 を追加してから、5609 を 5 で割って見る。割り切
れないので次の奇数に進む。
3.上記を繰り返す。下から試しているので、素数一覧が順にできあがって行く
ところがポイント。例えば途中の数 41 を試すときは、それより小さい素数
「2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37」がリストアップされてい
る。41の平方根は6.4…なので、2, 3, 5 だけ試せば充分。このどれでも割
り切れないので41は素数であることが解る。素数一覧に追加してから、5609
が41で割り切れるか試す。割り切れないので次の奇数に進む。
4.このまま、74まで行くかと思ったら、71（71の平方根は8.4…なので、2, 3,
5, 7 で割ってみて、どれでも割れないので素数）で割れる事が判明。よっ
て5069は素数ではなかった。
上の例では、ゴールを解りやすくするために、先に平方根を計算して各素数
が平方根を超えないことを確認しましたが、要は割ろうとする素数を２乗した
値が判定対象となる数を超えたところで止めれば言い訳です。例えば41が素数
であるかどうかを判定する場合は、2からスタート → 2×2 < 41 なのでまだ
→ 2で割れるか？ → 割れないので次の素数 → 3×3 < 41 なのでまだ → 3
で割れるか？ → 割れないので次の素数 → 5×5 < 41 なのでまだ → 5で割
れるか？ → 割れないので次の素数 → 7×7 > 41 なので終了 といった具合
になります。このように、次の素数に進む度に判定する方法は、先に平方根を
求める方法に比べて計算回数が増えますが、平方根を求める計算は時間がかか
るので、こちらの方が楽な方法です。
今のやりかたをもっと効率的にシステマティックに行う方法が「エラトステ
ネスのふるい」です。名前から想像が付くかと思いますが古代ギリシャの人（
BC200年前後）が考えたとされている方法です。「エラトステネスのふるい」
の目的は素数の判定というよりは、指定された数ｎより小さい素数を全て求め
ることにあります。手順は単純なのですが、画面上でやろうとすると面積が必
要な方法なので、先程の 5069 を例に検証するのは避けて、100以下の素数を
全て求める方法を例に説明します。
1.まず２から100の数を全て書きます。
2.最初の２は素数なので○を付けます（下の一覧では[]）。同時に２の倍数は
すべて×です。
[ 2] 3 × 5 × 7 × 9 ×
11 × 13 × 15 × 17 × 19 ×
21 × 23 × 25 × 27 × 29 ×
31 × 33 × 35 × 37 × 39 ×
41 × 43 × 45 × 47 × 49 ×
51 × 53 × 55 × 57 × 59 ×
61 × 63 × 65 × 67 × 69 ×
71 × 73 × 75 × 77 × 79 ×
81 × 83 × 85 × 87 × 89 ×
91 × 93 × 95 × 97 × 99 ×
3.この時点で 2の2乗(=4)より小さい数で×ないものは素数です。
4.確定した素数（現時点では 3 だけです）それぞれについて「○を付け、倍
数に×を付け、２乗以下の残った数を素数と確定」を繰り返します。ここで
は 5 と 7 が素数確定です。
[ 2] [ 3] × [ 5] × [ 7] × × ×
11 × 13 × × × 17 × 19 ×
× × 23 × 25 × × × 29 ×
31 × × × 35 × 37 × × ×
41 × 43 × × × 47 × 49 ×
× × 53 × 55 × × × 59 ×
61 × × × 65 × 67 × × ×
71 × 73 × × × 77 × 79 ×
× × 83 × 85 × × × 89 ×
91 × × × 95 × 97 × × ×
5.先程確定した 5 と 7 で同様のことを行うと 7×7=49 までの素数が確定し
ます。ここで確定した最初の素数 11 の段階で 11×11 > 100 となるのでこ
れ以上は判定する必要はありません。よってこの時点で残っている数が100
以下の素数です。
[ 2] [ 3] × [ 5] × [ 7] × × ×
[11] × [13] × × × [17] × [19] ×
× × [23] × × × × × [29] ×
[31] × × × × × [37] × × ×
[41] × [43] × × × [47] × × ×
× × [53] × × × × × [59] ×
[61] × × × × × [67] × × ×
[71] × [73] × × × × × [79] ×
× × [83] × × × × × [89] ×
× × × × × × [97] × × ×
実際にやってみると解ると思いますが、この方法はルールがもの凄く単純な
のですが、もし紙でやろうとすると結構体力を使う方法です。例えば、先程の
例を10倍して1000までの素数を求めるためには、1000の平方根は 31.6… なの
でそれより小さい「2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31」のわずか11個
の素数に関して先程の操作を繰り返すだけで済みますが、1000個（偶数は最初
から除けておくとしても500個）の数を書いて電卓を叩きながら×を書いて行
くだけでも大変な作業だというのは、容易に想像が付くのではないでしょうか。
この単純作業は人間よりもPCの方がずっと得意なのは言うまでもありません。
「エラトステネスのふるい」はプログラムを学習する人に出される練習問題と
して、最もポピュラーなものの１つです。例えば、表計算ソフトのエクセルで
も1000までの素数表を表示するスクリプトが作れるんじゃないかと思われます。
すみません。「エラトステネスのふるい」の話を引っ張り過ぎました。素数
の話というのは、こういった算数レベルの話から研究者レベルの話まで山ほど
ネタはあるのですが、切りがありませんので、これくらいにして次の素因数分
解の話に移ることにします。
-- 素因数分解の話 ----------------------------------------------------
素因数分解とは、整数を素数の積に分解することを言います。そんなの解っ
てるよって方はここでお別れです。後編では素因数分解の結果から約数の数を
求める方法から始まってゴールの「1000以下の数で約数が最も多いものは何か？
」までお話致しますので、そちらをお待ちください。
さて、素因数分解とは整数を素数の積に分解することを言います。つまり、
整数を素数だけを使った掛け算で表すわけです（それほど言い換えになってま
せんでした）。具体的な例を挙げます。12を何でも良いから掛け算で表してみ
ましょう。ただし、１は使っちゃ駄目です。例えば １２＝２×６ です。２は
素数なのですが６は素数ではありませんので、更に掛け算で表すと、６＝２×
３なので、結果として １２＝２×２×３ となりました。これが１２の素因数
分解です。大丈夫ですか？怒ってないですか？
骨休めに、少しだけ高度な話をします。「素因数分解は、必ず同じ結果にな
ることを証明しましょう。ただし、１２＝２×３×２のように順番を変えただ
けの場合は同じと見なします」だとちょっと数学ぽい問題になります。この証
明は背理法（「もしも、中尾彬がマクドナルドの店員だったら」のような「も
しもシリーズ」をヒントに考えられた証明方法）で証明するのが楽だと思われ
ます。中学生だった頃を思い出して証明にチャレンジしてみるもの一興でしょ
う。
さて、次は素因数分解の方法の説明と行きたいところですが、その前に累乗
の表記方法について説明しておかなければいけません。累乗（冪乗とも言われ
ます）とは、同じ数を何回も掛けるという計算です。階乗(*2)と言い間違える
人が居るらしいのでご注意下さい(*3)。累乗は掛けられる数の右上に掛ける回
数を書いて表します。このメールマガジンのように、文字サイズと位置を変え
ることができない場合は、＾を使います。例えば、２×２×２は２を３回掛け
てるので、 2^3 と表記します。また累乗は掛け算や足し算に優先するという
決まりがあります。例えば、 2^3 + 3 は 2×2×2＋3 です。２を３＋３回つ
まり６回掛けると敢えて書きたい場合は、 2^(3+3) と書きます。
*2 どんどん話がそれますが、階乗は「ある数を１になるまで１つずつ減
らしながら掛けた数」の事です。具体的には、５の階乗は５×４×３×２
×１＝１２０です。５の階乗を 5! と書きます。と行きがかり上、説明し
ましたが階乗の話は前後編ともに出てきません。
*3 もうひとつ階乗の話。ある方が日記で「『データの長さは２の階乗に
なるようにしておけ』と言われたので『じゃあ、２ですね』と答えた」と
書いていました。偉いです。
話が逸れたついでに累乗に関する小ネタをひとつ。2^0, 2^(-1), 2^2.5 が
それぞれどんな数になるか、理由も含めて考えてみてください。
最後に、素因数分解の方法について説明します。とは言っても素因数分解は
実に単純な方法を用います。簡単に言ってしまえば「ひたすら素数で割る」こ
れに尽きます。以下、1584の素因数分解を例に説明します。
1.小さい素数から順に割っていきます。まずは2で割ると 1584÷2=792。まだ
まだ2で割れます、792÷2=396、396÷2=198、196÷2=99。
2.もう2で割ることができなくなったので、次の素数3で割ります（3×3＜99な
ので、まだ約数が存在します）。99÷3=33、33÷3=11。
3.ここで、2でも3でも割れなくなりました。次の素数は5ですが、5×5＞11 な
のでもう約数はありません。よって、
1584=2×2×2×2×3×3×11=2^4 * 3^2 * 11
となります。今の例を一般化して整理すると、次のようになります。
素因数分解を行う際は最小の素数２から順に次の操作を繰り返します：
1.割れなくなるまで、その素数で割る。
2.割れなくなったら次の素数を求める。
3.次の素数の2乗が割られる数を超えたら終了。超えなかったら1へ。
なお「次の素数」を求める際には、あらかじめ素因数分解を行いたい数の平
方根までの素数一覧を先ほどの「エラトステネスのふるい」を使って用意して
おくのも手ですが、大抵はそこまでの素数表を準備しても、大きな素数は無駄
になる場合が多いので、上記の手順１が終わる毎に「エラトステネスのふるい
」のステップを進めて、次の素数を求める方が遙かに効率的です。
ここまでで、だいたい準備の説明は終わりました。前編はここまでとして、
本題の素因数分解の結果から約数の数を求める方法については後編でお話しま
す。
http://d.hatena.ne.jp/motomachi24
元町二十四軒
----------------------------------------------------------------------
おしらせ
----------------------------------------------------------------------
ＭＲＭ Vol.006は以上で終わりです。最後までお読み頂き、ありがとうござ
いました。
さて、次回の予告です。2/23 に発行予定の Vol.007では、Vol.005に掲載し
た質問３へお寄せ頂いた回答（現在４名、まだ間に合います）と質問４を掲載
する予定です。Vol.005についてはこちらをご覧ください。
→ http://gadd9.com/mrm/005.html
後編はVol.007の次になる予定です。それでは「ＭＲＭ Vol.007」でお会い
致しましょう。
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
・MRM [ MOTOMACHI RADIO MAIL ] Vol.006
発行部数 Web:計測不能 / メール:４通
発行 元町二十四軒
編集 元町二十四軒
・購読方法については、http://gadd9.com/mrm/ をご覧ください。バックナン
バーも同じページから見ることが出来ます。
・お問い合わせ、寄稿は motomachi24@nifty.com 宛にお願い致します。
・寄稿に当たっては、掲載するお名前・肩書き（架空で構いません）・サイト
のURL（掲載希望の場合）も併せてお知らせ頂けると幸いです。
・内容を許可無く転載することを禁じます。
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Copyright(C)2005 MOTOMACHI. All rights reserved.