【VBA】素数判定と素因数分解

記事後半に掲載されている「素数を並べるマクロ」と「素因数分解マクロ」を使用する場合、素数を判定する PRIME関数もコピーしてモジュールに貼りつけておいてください。

【VBA】素数を判定するユーザー定義関数

　指定した引数が素数であれば 1 , 素数でなければ 0 を返す 素数判定関数 を作成します。計算を高速化するために「合成数 $n$ は $p\le \sqrt{n}$ を満たす素因数 $p$ をもつ」という基本定理を用います。プログラムの流れは次のようになります。

1.入力された値が 2 ならば「素数」と判定して計算を終了します。
 
2.入力された値が 1 ならば「素数ではない」と判定して計算を終了します。
 
3.入力された値が 2 で割り切れたら偶数なので、「素数ではない」と判定して計算を終了します。
 
4.入力された値 n が √n < 3 となる奇数 3, 5, 7 については、「素数」と判定して計算を終了します (For…Next が処理されません)。

5. 以上の条件に当てはまらない数について、入力された値を奇数 k = 3, 5, 7, … で順に割り、割り切れた段階で「素数ではない」と判定して計算終了します。√n に達するまで１度も割り切れなかった場合は「素数」と判定します。

'[VBA] 素数判定関数

Function PRIME(n As Long) As Long

　　Dim m As Long
　　Dim k As Long
　　Dim ct As Long

　　m = Int(Sqr(n))

　　If n = 2 Then
　　　　PRIME = 1
　　ElseIf n = 1 Or n Mod 2 = 0 Then
　　　　PRIME = 0
　　　　Exit Function
　　End If

　　For k = 3 To m Step 2
　　　　If n Mod k = 0 Then
　　　　　　PRIME = 0
　　　　　　Exit Function
　　　　End If
　　Next k

　　PRIME = 1

End Function

PRIME関数の使い方は簡単です。たとえばシートのセルに

=PRIME(13)

と入力すると、13 は素数なので「 1 」が返ります。

=PRIME(24)

と入力すると、24 は素数ではないので「 0 」が返ります。
 
PRIME関数を用いて 1 ～ 100 までの素数を並べて書きだすマクロを書いてみます。

'[VBA] 素数を書きだすプログラム

Sub Prime_List()

　　Dim k As Long

　　For k = 1 To 100
　　　　If PRIME(k) = 1 Then
　　　　　　Debug.Print k;
　　　　End If
　　Next k

End Sub

Prime_List() を実行すると「2　3　5　7　11　13　17　19 …」のように 97 までの素数が表示されます。

【VBA】素因数分解

任意の数値を与えて素因数分解するマクロです。

Option Base 1

'[VBA] 素因数分解プログラム

Sub Factorization()

　　Dim m As Long, n As Long
　　Dim j As Long, k As Long
　　Dim prm() As Long

　　j = 1
　　k = 3

　　n = InputBox("自然数を入力してください")

　　If n <= 0 Then
　　　　MsgBox ("入力できるのは自然数のみです")
　　　　Exit Sub
　　End If

　　'配列の要素数をlog2nとする（底をeに変換しています）
　　m = Int(Log(n) / Log(2)) + 1

　　ReDim prm(m + 1)

　　For s = 1 To m
　　　　'nが素数なら計算終了
　　　　If PRIME(n) = 1 Then
　　　　　　j = j + 1
　　　　　　prm(j) = n
　　　　　　Debug.Print prm(j);
　　　　Exit For

　　　　'nが2で割り切れるなら、素因数2を配列に入れます
　　　　ElseIf n Mod 2 = 0 Then
　　　　　　n = n / 2
　　　　　　j = j + 1
　　　　　　prm(j) = 2
　　　　　　Debug.Print prm(2);

　　　　'nがkで割り切れて、かつkが素数ならば素因数kを配列に入れます
　　　　ElseIf n Mod k = 0 And PRIME(k) = 1 Then
　　　　　　n = n / k
　　　　　　j = j + 1
　　　　　　prm(j) = k
　　　　　　Debug.Print prm(j);

　　　　Else
　　　　　　'nがkで割り切れなくなったらkの値に2を加えます
　　　　　　k = k + 2
　　　　End If

　　Next s

End Sub

Factorization() を実行すると数値の入力が促されます。たとえば「488964」と入力してみると、「2　2　3　7　5821」のように素因数が並びます。