試し割り法(素因数分解&決定的素数判定アルゴリズム)｜Excel VBAで学ぶ数学とアルゴリズム

今回は素因数分解アルゴリズムかつ決定的素数判定アルゴリズムの「試し割り法」について解説していきます。試し割り法は素因数分解をするためのアルゴリズムですが、素因数分解をすればその数が素数であるかも同時に判定することができるため素数判定アルゴリズムにも分類されるアルゴリズムです。

アルゴリズムとしては「入力値を小さい自然数から順に割っていき割り切れるか割り切れないかを網羅的に確認していく」というだけの非常に単純なアルゴリズムです。

本ページではこの「試し割り法」のアルゴリズムがどういった仕組みなのかを解説し、最終的にExcel VBAのコードとして実装していきます。

1. 試し割り法
2. サンプルコード
3. まとめ

試し割り法

試し割り法とは入力された値の素因数を求めるためのアルゴリズムですが、ある自然数を素因数分解をしたときに素因数が1つであれば素数、複数あれば合成数と判断できることから素数判定アルゴリズムにも分類されるアルゴリズムです。

ちなみに素数判定アルゴリズムは大きく分けて「決定的素数判定」と「確率的素数判定」の2種類ありますが、この試し割り法はどの自然数に対しても確実に素数判定を行うことのできる、”決定的”素数判定に属されます。(確率的素数判定の代表としてフェルマーテストというアルゴリズムがあります)

試し割り法のアルゴリズムは非常に単純で下記の処理を行います。

① 入力値(自然数)を \(n\) に代入する
② \(n\) を \(i\) で割る ( \(i\) の初期値は2)
　・「余り＝0」の場合、素因数として \(i\) を配列に格納して\(n\) を \(n ÷ i\) の商に更新する
　・「余り≠0」の場合、\(i\) を \(i + 1\)に更新する
③ \(i\) が \( \sqrt{n} \) を超えるまで②を続ける
④ \(n\) の値が1より大きい場合は最後の素因数として\(n\) を配列に格納する
⑤ 配列の要素数を確認して1つであれば入力値は素数と判定

処理としては名前の通り「ある自然数(入力値)を小さい自然数から順番に割っていき、余りなくきれいに割り切れるかを試してみる」ということを繰り返しつづけるような内容となっています。

ここではさらに具体的な例で処理の流れを見ていきましょう。

―「60」が素数かを判定 ―

入力値として「60」を取得
素因数を格納するための配列を用意
割られる数を「n」割る数を「i」として変数を用意
初期値として「n=60, i=2」を代入
　
① 60を2で割る ⇒「余り=0」なので2を配列に格納し、nの値を30(=60÷2)に更新
② 30を2で割る ⇒「余り=0」なので2を配列に格納し、nの値を15(=30÷2)に更新
③ 15を2で割る ⇒「余り≠0」なので nの値はそのままで i の値を+1する
④ 15を3で割る ⇒「余り=0」なので3を配列に格納し、nの値を3(=15÷3)に更新
⑤ 5を3で割る ⇒「余り≠0」なので nの値はそのままで i の値を+1する
⑥ 5を4で割る ⇒「余り≠0」なので nの値はそのままで i の値を+1する
⑦ 5を5で割る ⇒「余り=0」なので5を配列に格納し、nの値を1(=5÷5)に更新
⑧ 1を5で割る ⇒「余り≠0」なので nの値はそのままで i の値を+1する
⑨ 1を6で割る ⇒「余り≠0」なので nの値はそのままで i の値を+1する
⑩ 1を7で割る ⇒「余り≠0」なので nの値はそのままで i の値を+1する
⑪ 1を8で割る ⇒「余り≠0」なので nの値はそのままで i の値を+1する
※ √60 ≒7.746 のためそれを超える最小の自然数の8までの確認でOK
　
⑫ nの値が1なので配列内にはすべての素因数が格納されていると判定
　(※ここでnが1より大きい値の場合はその値も素因数の1つとなる)
⑬ 入力値60は素因数が「2,2,3,5」の4つあるため素数ではない

このように小さい自然数から順に”余りなくきれいに割り切れるか”を見ていき「割り切れれば素因数、割り切れなければ次の自然数で確認」というように網羅的に確認していくアルゴリズムです。
こう見るとアナログで素因数分解する流れと全く同じであることがわかります。

上記の例の場合、\( \sqrt{60} = 7.746 \) を超える最小の自然数である8を確認した時点で終了したとしてもすべての要素を確認したことになります。
　

判定が√nまでで十分な理由

nが何らかの自然数pで割り切れる場合、その商となる自然数qを使って「n=pq」というような式で表すことができます。このアルゴリズムは小さい自然数から順に素因数か(割り切れるか)を確認していくため、qがpより小さい場合(p>q)には既に素因数として検出されているはずです。

たとえば「6=2×3」を調べた時点で6の素因数は「2と3」ということがわかります。
このとき「6=3×2」を調べても良いですが内容としては「6=2×3」と重複しており、わざわざ調べる必要はありません。これは「n」の値がどれだけ大きくなってもいえることです。

つまり「n=pq」を確認すれば実質「n=qp」も同時に確認したことになるため、pとqが一致する数値である√nまで確認すればすべての素因数を確認することができるというわけです。
　

巨大な素数と処理時間

試し割り法は網羅的に素因数かどうかを1つずつ確認していくアルゴリズムのため、場合によっては処理時間が非常にかかってしまいます。

たとえば、入力された数値が14桁の素数「67280421310721」であった場合、2で割り切ることができるか、3で割り切ることができるか、4で割り切ることができるか…と調べていき最終的には「8202465 (≒√67280421310721)で割り切ることができるか」まで確認する必要が出てきます。

上記くらいの数値であれば判定は一瞬ですが、この入力値が非常に巨大な素数(もしくは最小の素因数が非常に巨大な合成数)の場合にはその数値の平方根回ループして確認する必要がでてきてしまうため、入力値によっては数日、数カ月かかることもありえてしまいます。

ただそもそものお話、それほど巨大な数だとVBAがオーバーフローしてしまうので実現が難しいです。
そのためVBAで処理できる程度の数値であれば所為時間はあまり意識しなくても問題ありません。

参考：巨大な素数の一覧

サンプルコード

試し割り法をVBAで書くと下記の通りです。
入力された自然数の素因数は配列「iPrimeFactors」に小さい自然数順に格納され、その素因数の数が１つであれば素数と判定します。(※入力される自然数は2以上であることが前提となっています)

Sub main()

    Dim p As LongLong '大きい数字にも対応できるようLongLong型で宣言
    p = 123456789

    '試し割り法
    If TrialDivision(p) = True Then
        Debug.Print p & "は素数"
    Else
        Debug.Print p & "は合成数"
    End If
    
End Sub

'------------------------------------------------------------------
'   試し割り法(素因数分解)
'       n       ：判定する自然数
'       戻り値  ：[True]素数, [False]合成数
'------------------------------------------------------------------
Function TrialDivision(ByVal n As LongLong) As Boolean
    
    Dim iPrimeFactors()
    Dim i As Long
    
    '素因数格納用の配列を初期化
    ReDim iPrimeFactors(0)
    
    '試し割り法(素因数分解)
    For i = 2 To (Int(Sqr(n)) + 1)
    
        'nがiで割り切れなくなるまでiで割り続ける
        Do While n Mod i = 0
        
            'nがiで割り切れる場合,iはnの素因数なので配列に格納
            iPrimeFactors(UBound(iPrimeFactors)) = i
            ReDim Preserve iPrimeFactors(UBound(iPrimeFactors) + 1)
            
            'nの値を更新
            n = n \ i
        Loop
        
    Next i
    
    '最後まで割り切れなかった数値を
    If n > 1 Then
        iPrimeFactors(UBound(iPrimeFactors)) = n
    End If
    
    '配列の最後が空の場合は削除する
    If IsEmpty(iPrimeFactors(UBound(iPrimeFactors))) = True Then
        ReDim Preserve iPrimeFactors(UBound(iPrimeFactors) - 1)
    End If
    
    '素因数が1つの場合は素数
    If UBound(iPrimeFactors) = 0 Then
        TrialDivision = True
    Else
        TrialDivision = False
    End If
    
End Function