素数に恋する女

♥第4話♥

素数とはExcelで見つけられる数である

まゆ:そろそろ、ともの本気を見せてもらおうかな

とも:本気って何?

まゆ:あんたのExcelスキルを総動員して、ずばり素数を見つけるねん。ある数を入力したら、それが素数かどうか判定するだけでええんやけど…

とも:はぁ? 前に、1つの式ですべての素数を見つける方法はないって言ってなかったっけ?

まゆ:ないけど、パソコン使ったらなんとかなるんとちゃうの? Excelって、そぉいうもんやろ?

とも:Excelは素数探すためのソフトやないでw とはいえ、複数の式で見つけられるんやったら、できなくはないかも

まゆ:そやろ

とも:ちょっと待った!その前に、私、素数を見つける式とか、知らんやん

まゆ:簡単簡単。ある数を素数判定したかったら、2から、その数までの整数で割り算を繰り返せばええねん。割り切れなかったら素数

とも:いやいやいや。ざっくりしすぎやw 「10,000」とか入力されたら10,000回も割り算を繰り返すんか?

まゆ:10,000はExcel使うまでもなく素数やないから大丈夫

とも:ごめん、私が悪かったw じゃあ「10,001」が入力されたら、10,001回も割り算するんか?パソコンが非力やったら、Excel死ぬわ

まゆ:実際は、そんなに計算せぇへんで。最初の2で割る計算やけど、2で割れたら、その時点で素数ではないので終わり

とも:10,001は、私でも、一目見ただけで、2で割れないことぐらいわかるわ

まゆ:2で割れなくても大丈夫。2で割れないとわかった時点で「偶数で割れない」ので、偶数での割り算はしなくてもええで

とも:半分に減ったと言っても約5000回は計算せんといかんやん

まゆ:裏技があるんよ。裏技がw

話が長くなるので、まゆの話をまとめると、素数は基本的に次の手順で判定できる。

まゆ:実はnを素数判定したかったら√nまでの整数で割り算を繰り返せばええねん

とも:る、ルート?

まゆ:nが合成数やったら、nの約数同士を掛け算するとnになるペアが何種類かできるんやけど、そのペアを分けてるのが、実はnの平方根

まゆ:つまり、8と9の間に、素数判定の秘密が隠されている…と思わへん?

とも:どういうこと?

まゆ:72を例にすると、√72は少数で8.4852…になるんで、8と9の間に√72があるやろ。72は合成数なので√72までの整数で割り切れるけど、nが√nまでの整数で割り切れなければ、nは素数ということになるやん。

とも:なるほど。10,001を素数かどうか判定するには√10001までの整数。つまり100までの奇数で割り算を繰り返せばええんやな。

まゆ:厳密に言うならば100までの素数で割り算を繰り返せばええんやけど、そのやり方では、100までの数の素数判定もせんとあかんので、平方根までの全ての奇数での割り算が現実的やろなぁ。これぐらいやったら、Excelでできるんと違うん?

とも:できそうな気がするなぁ。どういう数式になるんか考えてみるわ

それっぽいのをExcelの数式にすると、下記のようになる。(※3)
=IF(A1=0,"←のセルに数を入れてみ?",IF(A1=2,"は素数やん!",IF(AND(MOD(A1,ROW(INDIRECT("2:"&ROUNDUP(SQRT(A1),0))))<>0),"は素数やん!","は素数と違うわ!残念やなぁ")))

【コピペ方法】

【使い方】

JavaScript版素数判定ツール
処理は端末に依存するため、スマートフォン等では利用状況によってフリーズする場合もあります。

まゆ:で、10,001は素数なん?

とも:違うみたいよ(※4)

まゆ:ずばり素数を見つけようという話やのに、素数でない数を例にするなんて…。これまでの説明が台無しやん

とも:え、それって、私が悪いの?

Excelの数式だけで素数判定!!

♥ 脚注 ♥

※1 エラトステネスのふるい
 エラトステネス(BC276〜BC195)はギリシャの数学者。ある数が素数かどうか知りたい場合、その数を2から整数で順番に割り、最後まで割り切れなかった場合は素数であることを発見した。
 これを応用して、100までの素数をすべて見つける場合、1〜100までの数のうち、まず1を消し、次に2〜10までの数で順番に割り、2,3,5,7以外の数で割り切れた数を消して、残った数が100までの素数となる。これを「エラトステネスのふるい」という。
 つまり100までの数は、100までの割り算をしなくても、10までの数を順番に割ることで判断できる。勘のいい読者は気づいたと思うが、100を分解すると「10×10」。つまり10は100の平方根なので、10までの数を割ることで100までの素数を見つけることができるのだ。本文中の解説も基本は同じ原理である。

※2 割り算の回数について
 本稿では解説を簡単にするため、素数を判定する数(以下 n )の半分までの数を計算するとしているが、厳密には下記の段階を踏むため、割り算を繰り返す回数は、さらに減る。
・2で割り切れなかった場合
 次の計算(3で割るとき)は n × 1/3 までの奇数(正確には素数)まで割り算を繰り返す
・3で割り切れなかった場合
 次の計算(5で割るとき)は n × 1/5 までの奇数(正確には素数)まで割り算を繰り返す
・5で割り切れなかった場合
 次の計算(7で割るとき)は n × 1/7 までの奇数(正確には素数)まで割り算を繰り返す
これを繰り返して、割る数が、√ nを超えた時点で割り切れなければ、 n は素数である。

※3 参考
Test if a Number is Prime using a Formula in Microsoft Excel
 [A1]セルに入力された数字を、最小の素数である2〜[A1]セルの平方根までにある整数(処理上、小数点以下を切り上げている)で割り算を繰り返し、最後まで余りがあると素数と判定しています。ただし、これだけでは2を素数とみなさないため、2が入力されたときだけ、計算をせずに素数と判定しています。

※4 10,001が素数でない理由
素因数分解すると… 10,001 = 73 × 137
∴素数ではない (Q.E.D)

「素数に恋する女」公式Twitter

素数姫の素数入門
Last Update 2015/9/9 © 2015「素数に恋する女」製作委員会 All Rights Reserved.