[VBA] 素数判定と素因数分解

2017.03.07

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

[VBA] 素数を判定するユーザー定義関数

　指定した引数が素数であれば 1 , 素数でなければ 0 を返す 素数判定関数 を作成します。計算を高速化するために

　合成数 n は p ≤ √n を満たす素因数 p をもつ

という基本定理を用います。プログラムの流れは次のようになります。

　① 入力された値が 2 ならば「素数」と判定して計算を終了します。

　② 入力された値が 1 ならば「素数ではない」と判定して計算を終了します。

　③ 入力された値が 2 で割り切れたら偶数なので
　　「素数ではない」と判定して計算を終了します。

　④ 入力された値 n が √n < 3 となる奇数 3, 5, 7 については、
　　「素数」と判定して計算を終了します (For…Next が処理されません)。

　⑤ 以上の条件に当てはまらない数について、
　　入力された値を奇数 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 」が返ります。

[VBA] 素数を並べて書きだすマクロ

　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)

　　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

というように素因数が並びます。

コメント