ブックタイトルROOT No.19

概要

ROOT No.19

読み解く！数学偉人伝エラトステネス素数を効率よく発見できるアルゴリズムを考案●桐蔭横浜大学准教授城田直彦自然数を顕微鏡で見る！「12の約数っていくつあるかな？言ってごらん」取り組みやすいからでしょうか，この発問に生徒たちは生き生きと答えてくれます。答えは，6個です。「では，45の約数はいくつ？」12に比べて数が大きくなったので，約数の個数が増えると予想する生徒が多いのですが，結果は6個，12の場合と同じです。そこで，私は言います。「こんなときは，『顕微鏡で見る』とよくわかるんだ！」もうお分かりですね，私が「顕微鏡で見る」と称しているのは，「自然数をいくつかの自然数の積の形に分解すること」を意味しています。12と45を「これ以上分解できないところ」まで作業を進めると，それぞれ2 2×3，3 2×5となり，ともに○2×△の形になります。両者にはそういう共通点があったわけです。そして，今回の話題である「素数」は，「これ以上分解できない」という最終到達点として現れてきます。漏れ落ちのないように，ルールを決めてでは，ある自然数が素数であるかないかはどうやって判断すればよいのでしょうか。たいへん面倒なのですが，これはもう「試してみるしかない」という状況です。約数が１とその数自身だけの自然数が素数ですから，素数かどうかを判断するためには，約数を調べてみればよさそうです。その際には「漏れ落ち」がないように，たとえば「小さい数から順に調べる」というルールを持っておくのがよいと思います。たとえば，35の場合……，1 35は2では割り切れない2 35は3では割り切れない3 35は4では割り切れない4 35は5で割り切れる！→素数ではないこれで作業は完了！35は素数ではありません。この作業では，1～4まで似たようなチェックが続けられ，4で完了しています。このように，ある問題を解決するための方法や手順は，一般に「アルゴリズム」と呼ばれています。さらによいアルゴリズムを求めてじつは，先の3のチェックは省略できます。35が2で割り切れないことは，1でチェック済みです。2で割り切れない数は4でも割り切れないので，3のチェックは不要になります。したがって……，1 35は2では割り切れない2 35は3では割り切れない3 35は5で割り切れる！→素数ではない手数が減りました！先ほどより効率のよいアルゴリズムになったわけです。よく見ると，2,3,5……，素数が並んでいます。つまり，ある数が素数であるかどうかを判断するためには，その数よりも小さい素数で割り切れるかどうかを調べればよいわけです。素数のチェックに素数を使うなんてなんだか奇妙な感じですが，「既に分かっていることを利用すると，作業を効率化できる」というよい例です。6算数・数学情報誌ROOT vol.19