素数判定アルゴリズム VB Code (Primality Test Algorithm (VB code to find Prime number))

素数を判定して求めるアルゴリズムを紹介します。素数を求める数列式は現在のところ見つかっていませんので、求めた素数で割り切れるかどうかで判定します。改良されたアルゴリズムは、最小限の除算による判定回数で素数を求めることが出来ます。その２種類のプロシージャと、素数判定ファンクションのソースコードを紹介しています。

This algorithm is to judge and asks for a prime number. Since the sequence-of-numbers type which asks for a prime number is not yet found at present, it is judged whether it can divide among the prime number. The improved algorithm will find out a prime number by the minimum times of a judgment.Two kinds of the procedure and a function are shown below.

まず、最初に書いているコードは、2000までの素数を求めるプロシージャです。Forループの"For i = 5 To 2000 Step 2" の2000の部分を1000にすれば1000までの素数を求めます。予め範囲内の素数の数が分からないので、動的配列を使用して素数が見つかった場合のみ配列の要素を増やして格納します。このプロシージャの判定方法は、見つけて配列に格納された素数で割り切れるかどうかで判定しています（割り切れる数値で判定しても余計な処理になります）。格納された素数での総当りする方法ですので、アルゴリズムとしては低レベル（原始的）なものです。（総当り（Brute force)はアルゴリズムから除外されるべきです）

The code written first is a procedure which asks for the prime number to 2000. "For i = 5 To 2000 Step 2" if you set a range to 1000, it will ask for the prime number to 1000. It is judged whether this procedure can be divided among the prime number which was stored in array. Since it is the method in the stored prime number which carries out brute force, it is a thing of a low level as an algorithm. ("brute force" should be ruled out from algorithm)

２番目のプロシージャは、余計な除算判定を省略して処理回数を大幅に削減しています。ループ内でIf RESULT(j) ^ 2 > i Then Exit For を付け足しています。この意味は、例えば997が素数であるかを求める場合、{3,5,7,11,13・・・} と格納された3以上の素数で除算判定をしていくわけですが、見方を少し変えると、3*X---> 5*X---> 7*X---> 11*X---> 13*X とXに数値を代入して997になるかどうかを判定しているのと同じ意味です。31まで調べられたとき、次の素数は37になり、37*XのXは31よりも小さい数値になるはずです。31よりも小さい数値はそのとき既に除算判定されています。よって31よりも大きい素数での997を素数判定する必要はありません。

The 2nd procedure omits an excessive judging and is reducing a large number of times of processing. If RESULT(j) ^ 2 > i Then Exit For is added in For loop. For example, when you are asking for whether 997 is a prime number, {3, 5, 7, 11, 13} in an array, judging is carried out by three or more stored prime numbers. When it was judged to 31, the following prime number will be set to 37. X of (37 * X) should become a numerical value smaller than 31. The division judging of the prime number smaller than 31 has already been carried out. Therefore, it is not necessary to carry out the prime number judging of 997 in a larger prime number than 31.

The 3rd code is Function. This Function returns TRUE, when it is a prime number.

素数判定ファンクション（３番目のコード）：
このFunction は、素数である場合TRUEを返します。まず、数値が2、3である場合はTRUEを返し、2未満または偶数の場合はFalseを返すためのコードを書いてます。次に、3以上の奇数で除算判定していきます。ここでも、 If i ^ 2 > Num Then Exit For と不必要な処理を省きます。 簡単にMsgBox　PrimeNumber(997)と書けば997は素数なので戻り値はTRUEとなります。