[PR]当サイトはアフィリエイト広告を利用しています。
はじめに
今回は素因数分解をプログラムで求めてみようという回です。
中学校くらいで素因数分解はやるんですけど、プログラムで求めると意外と歯ごたえがあります。
まず手計算で素因数分解をやってみましょう。
28を素因数分解してみます。
まず28を最小の素数である2で割ります。
答えは14です。そのため答えリストに2をストックします。
次に答えの14をまた最初に戻って2で割ります。
答えは7です。答えリストに2をストックします。
次に答えの7を最初に戻って2で割ります。
割り切れないので7を次の素数の3で割ります。
割り切れないので4、5、6と割り切れるまで数値を上げていきます。
すると7で割り切れます。
答えリストに7をストックします。
答えと割る数が一致したので素因数分解を終了します。
見つかった素因数分解の答えは2、2、7となります。
アルゴリズム
これをアルゴリズムで表してみます。
(1)求めたい値を答えとしてセットする。
(2)答えを2から順に素数で割る。
（割り切れた場合）答えのリストに割り切れた素数を追加する。もし割り切れた素数と答えが一致したら(2)を終了する。
一致しなかったら、答えを（答えと割り切れた素数の商）にセットしなおす。
(2)の初めに戻る。
（割り切れなかったら）次の素数を割る数にセットする。(2)の初めに戻る。
(3)答えのリストを出力する。
作成したプログラム
素因数分解するプログラムは次のようになります。
Sub PrimeFactor()
Dim i As Integer
Dim k As Integer
k = 1
Dim s As Integer
s = Range("A2").Value
Dim temp As Integer
Dim prime() As Integer
ReDim prime(s) As Integer
Dim flag As Boolean
flag = Flase
Do While (flag = False)
For i = 2 To s
temp = judgement(i, s)
If (temp <> 0) Then
prime(k) = temp
If (temp <> s) Then
s = s / temp
Exit For
End If
End If
If (temp = s) Then
flag = True
Exit For
End If
Next i
k = k + 1
Loop
For i = 1 To (k - 1)
Cells(i + 1, 2).Value = prime(i)
Next i
End Sub
Function judgement(x As Integer, s As Integer)
If (s Mod x = 0) Then
judgement = x
Else
judgement = 0
End If
End Functionコードの解説
まず次の部分で初期設定を済ませます。
Dim i As Integer
Dim k As Integer
k = 1
Dim s As Integer
s = Range("A2").Value
Dim temp As Integer
Dim prime() As Integer
ReDim prime(s) As Integer
Dim flag As Boolean
flag = Flaseちなみに
Dim prime() As Integer
ReDim prime(s) As Integerの部分は配列を変数の数だけ用意するための書き方です。
そのまま
Dim prime(s) As Integer
と書くと動かないのでこういう書き方をします。
(1)の部分は
s = Range("A2").Valueでやっています。
次に(2)の部分です。
答えを2から順に素数で割る部分は
temp = judgement(i, s)です。
ここは関数で省力化します。
Function judgement(x As Integer, s As Integer)
If (s Mod x = 0) Then
judgement = x
Else
judgement = 0
End If
End Function割る数と答えを受け取って、割り切れたら割る数を返して、そうでないなら0を返します。
そうでないならの部分を他の答えと重複しない0で表現しました。
次に
——
（割り切れた場合）答えのリストに割り切れた素数を追加する。もし割り切れた素数と答えが一致したら(2)を終了する。
一致しなかったら、答えを（答えと割り切れた素数の商）にセットしなおす。
——
この部分。
If (temp <> 0) Then
prime(k) = temp
If (temp <> s) Then
s = s / temp
Exit For
End If
End If
If (temp = s) Then
flag = True
Exit For
End If割り切れた場合は
temp <> 0
です。
一致しなかったら、答えを（答えと割り切れた素数の商）にセットしなおすの部分は
If (temp <> s) Then
s = s / temp
Exit For
End If割り切れた素数と答えが一致したら(2)を終了するの部分は
If (temp = s) Then
flag = True
Exit For
End If終了させるためにflagをTrueにしてWhile文を抜けられるようにしています。
（割り切れなかったら）次の素数を割る数にセットする。(2)の初めに戻るの部分は
temp <> 0
の部分で判定しています。
割り切れなかったら
If (temp <> 0) Then
も
If (temp = s) Then
も実行されないので
For i = 2 To s
のiが一つ増加してプログラムが進みます。
この表現で素数を一つ増加させる処理を行っています。
まあ詳しい証明は省略します。
大雑把に言うと、最小の素数で答えを割り続けると素因数分解できるという話です。
最後に
For i = 1 To (k - 1)
Cells(i + 1, 2).Value = prime(i)
Next iここで答えのリストを出力して終了です。
k – 1にしているのは
While文の最後にk + 1があるので一つkが余計に加算されるためです。
実行してみると
ちゃんと
答えが
2、2、7
と求められていますね。
まとめ
今回は素因数分解をプログラムで実行してみようという回でした。
プログラムは一回手計算をやってみて、そこに動く法則みたいなものを見つけることから始まります。
まず2では動くからここまでは正しい。
でも3では動かないからこれを追加する。
さらに4では動かないからこれを追加する。
こうやって具体的な数値を順に試してみてプログラムが包括的な数値で動くか考えていきます。
