VBA

VBA – エラトステネスの篩を用いた最速素数アルゴリズムのVBA実装と高速なデータ出力

素数は数学や計算において非常に重要です。この記事では、Excel VBAを使用してエラトステネスの篩を実装し、高速に素数を見つける方法に焦点を当てます。また、その結果をテキストファイルやワークシートに効率的に出力する手法も解説します。

エラトステネスの篩 とは

エラトステネスの篩(エラトステネスのふるい、英: Sieve of Eratosthenes)は、古代ギリシャの数学者であるエラトステネスによって考案された素数を見つけるための効率的なアルゴリズムです。このアルゴリズムは、一定の範囲内の数に対して素数を効率的に見つけ出すことができるため、素数を求める古典的かつ高速な手法として知られています。

アルゴリズムの手順は以下の通りです

  1. 2から始めて、最初の素数である2を見つけます。
  2. 2の倍数(4, 6, 8, 10, …)を除外します。
  3. 次に残っている数である3を見つけます。
  4. 3の倍数(6, 9, 12, 15, …)を除外します。
  5. これを繰り返し、残っている最小の数を見つけ、その倍数を除外します。
  6. 繰り返しを終えるまで続けます。

このアルゴリズムを適用することで、最終的に残る数は素数になります。このアプローチの利点は、2から始めて倍数を順に除外していくため、重複する計算を避け、非常に効率的に素数を見つけ出すことができる点です。

エラトステネスの篩アルゴリズムの実装

Private Function PrimeNumbers(ByVal N As Long) As Variant
    ' N以下の素数をエラトステネスの篩で検出し、配列として返す関数

    Dim i As Long, j As Long
    Dim Max As Long
    Dim Flg() As Boolean    ' 素数判定用のフラグ
    Dim Pns() As Long       ' 素数の配列
    Dim C As Long

    If N < 2 Then
        PrimeNumbers = Array() ' 2未満の場合、空の配列を返す
        Exit Function
    End If
    
    ' フラグを初期化し、全てを素数と仮定する
    ReDim Flg(1 To N)
    For i = 1 To N
        Flg(i) = True
    Next
    
    ' 1は素数ではない
    Flg(1) = False
    
    ' チェックする最大値
    Max = Sqr(N)
    
    ' エラトステネスの篩アルゴリズム
    For i = 2 To Max
        If Flg(i) Then
            For j = i + i To N Step i
                Flg(j) = False
            Next
        End If
    Next
    
    ' 素数の数を数える
    C = 0
    For i = 1 To N
        If Flg(i) Then C = C + 1
    Next
    
    ' 素数を配列にセット
    ReDim Pns(1 To C)
    C = 0
    For i = 1 To N
        If Flg(i) Then
            C = C + 1
            Pns(C) = i
        End If
    Next
    
    PrimeNumbers = Pns
End Function

この関数は、エラトステネスの篩アルゴリズムを用いて、1からNまでの素数を検出します。そして、その素数を配列として返します。

テキストファイルへの高速なデータ出力

Sub PnsCallTest4()
    Dim Pns As Variant
    Dim T As Single
    Dim N As Integer, i As Long
    
    T = Timer

    ' 素数配列の取得
    Pns = PrimeNumbers(1 * 10 ^ 7)
    
    Debug.Print Timer - T
    
    N = FreeFile
    ' デスクトップのtest.txtへ
    Open CreateObject("WScript.Shell").SpecialFolders("DeskTop") & "\test.txt" For Output As #N
    
    For i = 1 To UBound(Pns)
        Print #N, CStr(i); ","; CStr(Pns(i))
    Next
    Close #N
    
    Debug.Print Timer - T
End Sub

このサブルーチンは、エラトステネスの篩を用いて素数を取得し、その結果をテキストファイルに高速に出力します。

シートへのデータ出力

Sub PnsCallTest3()
    Dim Pns As Variant
    Dim T As Single
    
    T = Timer
    
    ' 素数配列の取得
    Pns = PrimeNumbers(82 * 10 ^ 4)
    
    Debug.Print Timer - T
    
    ' 配列をN行1列に変換してシートへ
    If UBound(Pns) >= 0 Then
        ActiveCell.Resize(UBound(Pns)).Value = Application.WorksheetFunction.Transpose(Pns)
    End If
End Sub

このサブルーチンは、エラトステネスの篩を用いて素数を取得し、その結果をExcelワークシートに効率的に出力します。

まとめ

この記事では、エラトステネスの篩を用いた最速素数アルゴリズムのExcel VBA実装について解説しました。また、得られた素数データをテキストファイルやワークシートに高速に出力する手法も紹介しました。これにより、大量の素数データを扱う際に効率的で高速な処理が可能となります。