Excelで素因数分解

前回は、Excelで素数判定をやってみた。
infoment.hatenablog.com
なぜ、素数判定をやってみたか。そもそもの切っ掛けは、Excelで素因数分解って
どんな風にやれるかな？と思ったこと。

というわけで、やってみた。

素因数分解 (そいんすうぶんかい、英: prime factorization) とは、ある正の整数を素数の積の形で表すことである。

ja.wikipedia.org

そこで、二つの関数を作成してみた。

1. 引数で与えられた数に含まれる、素数とその数を収めた辞書
2. 1. の情報を元に、a^m*b^nのような表記を作成する関数

実際に作成したのがこちら。

' 素因数分解した結果を格納する辞書。
' keyに約数となる素数を、itemにその数を持つ。
Function PrimeFactorDict(num As Long) As Object
    Dim i As Long
    Dim iMax As Long
    
    Dim Dict As Object
    Set Dict = CreateObject("Scripting.Dictionary")
    
    Dim temp As Long
        temp = num
        ' tempの約数を探して、あればそれでtempを割って
        ' いく。tempが素数になるまで続ける。
        Do
            iMax = WorksheetFunction.RoundUp(temp ^ 0.5, 0)
            For i = 2 To iMax
                If temp Mod i = 0 Then
                    If Dict.Exists(i) Then
                        Dict(i) = Dict(i) + 1
                    Else
                        Dict(i) = 1
                    End If
                    temp = temp / i
                    Exit For
                End If
            Next
            
            ' 素数であればLoopを抜ける。
            If i > iMax Then
                Dict(temp) = 1
                Exit Do
            ' ２のべき乗対応。
            ElseIf i = iMax Then
                Dict(temp) = Dict(temp) + 1
                Exit Do
            End If
        Loop
    
    Set PrimeFactorDict = Dict
End Function

' 素因数分解の結果を文字列で出力。
Function PrimeFactorization(num As Long) As String
    Dim Dict As Object
    Set Dict = PrimeFactorDict(num)
    
    Dim arr() As Variant
    ReDim arr(1 To Dict.Count)
    
    Dim i As Long: i = 1
    Dim myKey As Variant
        For Each myKey In Dict.Keys
            If Dict(myKey) = 1 Then
                arr(i) = myKey
            Else
                arr(i) = myKey & "^" & Dict(myKey)
            End If
            i = i + 1
        Next
        
        PrimeFactorization = Join(arr, "*")
End Function

実際の計算結果がこちら。

割といい感じだ。次回に続きます。

参考まで。