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

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

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

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

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

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

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

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

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

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

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

'[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

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

コメント