素数判定を行うユーザー定義関数

今年（2011年）に入ってから、「2011」が素数であることから、それに関連したツイートやブログ記事を見かける機会が何度かありました。

VBA（Visual Basic for Applications）でも、素数かどうかを判定するユーザー定義関数を作ることは可能です。

ちなみに素数というのは、
「1よりも大きな、1と自分以外で割り切れない自然数」
です。

一番わかりやすい素数かどうかの判定は、2から、調べたいその数字から「1」をマイナスした値までの自然数で順番に割ってみて、割り切れるかどうかを調べればできます。

例えば、「11」が素数かどうかを調べるには、「2」から「10」までの自然数で割ってみて、割り切れなければ素数と判定できます。

この考え方をそのままVBAで書き起こせば、もっともわかりやすい素数判定ユーザー定義関数が、とりあえずできます。

素数は1よりも大きな自然数ですから、1以下の場合は素数ではありません。

変数宣言のすぐあとの
　If lngVal <= 1 Then IsPrimeNum_BASIC = False: Exit Function
の部分でこの判定を行っています。

メインの処理は、「2」から、調べたい数字から「1」マイナスした値まで順番に割り算してみて割り切れるか、すなわち、余りが「0」になるか調べていき、割り切れたら素数ではないと判断して処理をやめるというものです。

それがループ処理、
　For lngLop = 2 To lngVal - 1 Step 1
　　If lngVal Mod lngLop = 0 Then IsPrimeNum_BASIC = False: Exit Function
　Next lngLop
という部分の意味です。

ループ処理をやってみて、割り切れなかったら素数と判断できるので最後に
　IsPrimeNum_BASIC = True
としています。

しかしこれだけだと、「2」が素数ではないと判断されてしまうので、ループ処理に入る前に
　If lngVal = 2 Then IsPrimeNum_BASIC = True: Exit Function
で「2」だったら素数と判定して処理をやめます。

このユーザー定義関数の引数を
　ByVal lngVal As Long
と長整数型にしているので、整数でない数値が指定された時点で素数ではないと判断されます。

以上が、おそらく一番わかりやすい素数判定を行うユーザー定義関数でしょう。

問題はループ処理です。

調べる数値が大きくなればなるほどループを回す回数が増えてしまい、結果が出るまでに時間がかかってしまいます。

そこをどうするのかが、このユーザー定義関数のキモです。

ちょっと検索をしてみると、ユーザー定義関数ではありませんが、「ミカン色の空へ」というブログで、このループ処理を少なくする効果的な方法をいくつか組み合わせた「Excel VBAにおける素数判定プログラム（マクロ）」という記事が公開されていました。

「ミカン色の空へ」さんの考え方を取り入れさせていただいたのが、以下のユーザー定義関数です。

ループ処理が、
　For lngLop = 3 To Sqr(lngVal) Step 2
　Next lngLop
となっています。

「2」より大きな偶数は、「2」で割り切れるので素数ということはあり得ません。ですからループ処理を「1」加算しながら行うのではなく、「3」から、
　For lngLop = 3
「2」を加算しながら
　Step 2
行っています。

このロジックを取り入れるだけで、先のベーシックな方法に比べてループの回数は半分になります。（偶数を飛ばして奇数だけ処理するのですから）

更に効果的なのが、調べたい数字から「1」マイナスした値までではなく、調べたい数の平方根した値まで調べる
　To Sqr(lngVal)
という部分です。

調べたい数字から「1」マイナスした値まで割り切れるか調べたとしても、もし割り切れる場合には、平方根以下の数が含まれているため、調べたい数の「1」マイナスした値まで調べる必要はなく、調べたい数の平方根まで調べればいいのです。（この平方根まで調べればいいという部分は、Excelの話というより純粋な数学の話になるので、納得できない方は素数判定について書かれた数学系の文献をご参照ください。）

奇数だけチェックする、調べたい数値の平方根まで調べる、というここまでのループ処理を減らす考え方は、結構あちこちでみかけます。

私が先の「ミカン色の空へ」さんのマクロで面白いと感じたのは、ループ処理の中にもう一つループ処理をいれているところです。一部の奇数の処理を飛ばす処理を入れているところです。

「5」より大きい数値のときには、「3」または「5」で割り切れる数値の場合に、割り切れるかどうかの試行を飛ばすように
　If lngLop > 5 Then
　　Do While lngLop Mod 3 = 0 Or lngLop Mod 5 = 0
　　　lngLop = lngLop + 2
　　Loop
　End If
としています。

この処理を入れるだけで、ループ回数は確実に減らせます。

たとえば、「3」「5」または「7」で割り切れる奇数の場合に処理を飛ばすように
　If lngLop > 7 Then
　　Do While lngLop Mod 3 = 0 Or lngLop Mod 5 = 0 Or lngLop Mod 7 = 0
　　　lngLop = lngLop + 2
　　Loop
　End If
などとすれば、更にループ回数は減らせます。

こういう処理はどこまで入れるのか、かなり個人の趣向に関係してくる領域です。

▼サンプルファイル（003810.xls 36KByte）ダウンロード

サンプルファイルには、上記のIsPrimeNum_BASIC関数とIsPrimeNum関数を作成して、A列の値を参照してB列にIsPrimeNum_BASIC関数による判定結果、C列にIsPrimeNum関数による判定結果を表示させてありますので、興味のある方はご確認ください。

なお、
A15セルには、これらのユーザー定義関数で素数かどうか判定できる、もっとも大きな自然数「2,147,483,647」を入力して、
　B15セルに「=IsPrimeNum_BASIC(A15)」
　C15セルに「=IsPrimeNum(A15)」
という数式をそれぞれ入力して、B15セルは先頭に「'」（シングルクォーテーション）を入れてテキストにしてあります。

シンプルな素数判定のユーザー定義関数IsPrimeNum_BASICだと、「2,147,483,647」のように大きな数値の判定を行うのに、どれくらい時間がかかってしまうのかを実感してみたいという方は、B15セルの先頭の「'」を削除して［Enter］キーを押してみてください。

ただし、
マシンスペックによっては、ものすごーく時間がかかってしまいますから、試してみたいという場合、最悪Excelを強制終了させてもいいような準備をしてから行うことを、強くおすすめします。