素数とは
1とその数自身でしか割り切れない数です。
まずは2から a までの正数に含まれる素数を調べます。
下のコードでは、a = 1000で
2から1000までの正数に含まれる素数を調べています。
大まかな考え方は次のようになっています。
ある正数 i を
2から i までの正数 j で順に割っていく。
余りが0、つまり割り切れたとき
i <> j ならば、i は i 以外の数で割り切れたので素数でない、
i = j ならば、i は素数。
コードはこちら
素数を調べるコード：Sub macro101211a()
'素数を調べる
Sheets.Add.Name = "macro101212a"
Cells(1, 1) = "素数"
Dim i As Long, j As Long
Dim a As Long
'2からaまでの正数を調べる
a = 1000
For i = 2 To a
For j = 2 To i
If (i Mod j) = 0 Then
If i = j Then
'iは素数
Rows(2).Insert
Cells(2, 1) = i
Else
'1とその数以外で割り切れる場合
'その数(i)は素数でないので
'次の数へ
GoTo NextNum
End If
End If
Next j
NextNum:
Next i
End Sub |
実行後のシート
次はある正数を素因数分解したいと思います。
素因数分解とは次のようなことです。
18 = 2 * 3 * 3
大まかな考え方は次のようになっています。
ある正数 x を
2から x までの正数 i で順に割っていき
一番最初に割り切れる i が素因数。
x をその i で割って商が1でないなら
x = x / i にして
再度2から x までの正数 i で順に割っていき
素数を調べる。
これをx = 1になるまで繰り返す。
コードはこちら
素因数分解するコード：Sub macro101211b()
'Option Base 1で実行
'素数に分解して
'その素数を配列に入れる
Dim i As Long
Dim x As Long '素数に分解する正数(>=2)
Dim x2 As Long '操作用のｘ
Dim count As Integer '配列の添え字用
Dim PNum() As Long '素数を入れる配列
Dim Str As String
count = 1
x = 18
x2 = x
ReStart:
For i = 2 To x2
If x2 Mod i = 0 Then
'iはxの素数
ReDim Preserve PNum(count)
PNum(count) = i
x2 = x2 / i
count = count + 1
GoTo ReStart
End If
Next i
'結果出力用文字列作成
Str = x & " = "
For i = 1 To UBound(PNum)
Str = Str & PNum(i) & " * "
Next i
Str = Left(Str, Len(Str) - 3)
MsgBox Str
End Sub |
実行結果例
素因数分解までしたら
最大公約数、最小公倍数を調べます。
まずは、素因数分解の仕方を上のプロシージャから変更して
同じ素数の掛け合わせは累乗で表現します。
たとえば18なら2*3^2なので
次のように表現します。
２つの数の最大公約数、最小公倍数ですので
素数、1つ目の数の指数、2つ目の数の指数の順に並べます。
最大公約数は
２つの数に共通でない素因数は捨て、
２つの数の共通な素因数の次数の低いものを掛け合わせたもの。
また、最小公倍数は
２つの数に共通でない素因数はそのまま取り、
共通な素因数はその次数の高いものを選んで掛け合わせたもの。
この定義から最大公約数、最小公倍数を求める大まかな流れを考えます。
最大公約数は
2つの数の指数が共に0でないとき
小さいほうの指数を取って
該当する素因数を累乗したものを掛けていく。
最小公倍数は
2つの数の指数の大きいほうの指数を取って
該当する素因数を累乗したものを掛けていく。
２つの数に共通でない素因数の場合も
０か１以上の比較なので
単純に大きいほうを取っていけばよい。
コードはこちら
最大公約数、最小公倍数を求めるコード：Sub macro101211c()
'Option Base 1で実行
'素数に分解して
'その素数を配列に入れる
Sheets.Add.Name = "macro101211c"
Dim i As Integer
Dim j As Integer
Dim a As Integer
Dim x(2) As Integer '素数に分解する正数(>=2)
Dim x2 As Integer '操作用のｘとy
Dim count As Integer '配列の添え字用
Dim PNum(20, 3) As Integer '素数を入れる配列
'素数の種類は20まで対応
Dim Str As String '結果出力用文字列
Dim GCM As Integer '最大公約数
Dim LCM As Integer '最大公倍数
count = 1
x(1) = 42
x(2) = 135
For a = 1 To 2
x2 = x(a)
Step1:
For i = 2 To x2
If x2 Mod i = 0 Then
'iはxの素数
For j = 1 To UBound(PNum, 1)
If i = PNum(j, 1) Then
PNum(j, a + 1) = PNum(j, a + 1) + 1
GoTo Step2
End If
Next j
PNum(count, 1) = i
PNum(count, a + 1) = 1
count = count + 1
Step2:
x2 = x2 / i
If x2 <> 1 Then
GoTo Step1
End If
End If
Next i
Next a
'最大公約数
GCM = 1
LCM = 1
For j = 1 To UBound(PNum, 1)
If PNum(j, 1) <> 0 Then
If PNum(j, 2) <> 0 And PNum(j, 3) <> 0 Then
If PNum(j, 2) < PNum(j, 3) Then
GCM = GCM * PNum(j, 1) ^ PNum(j, 2)
Else
GCM = GCM * PNum(j, 1) ^ PNum(j, 3)
End If
End If
Else
GoTo Step3
'素数の列が0になったところで終わり
End If
Next j
Step3:
'最小公倍数
For j = 1 To UBound(PNum, 1)
If PNum(j, 1) <> 0 Then
If PNum(j, 2) > PNum(j, 3) Then
LCM = LCM * PNum(j, 1) ^ PNum(j, 2)
Else
LCM = LCM * PNum(j, 1) ^ PNum(j, 3)
End If
Else
GoTo Step4
'素数の列が0になったところで終わり
End If
Next j
Step4:
'シートに書き出す
Cells(1, 1) = "素数"
Cells(1, 2) = "x(1) = " & x(1)
Cells(1, 3) = "x(2) = " & x(2)
Range("A2").Resize(UBound(PNum, 1), UBound(PNum, 2)) = PNum
Cells(1, 4) = "最大公約数"
Cells(1, 5) = "最小公倍数"
Cells(2, 4) = GCM
Cells(2, 5) = LCM
End Sub |
実行後のシートの例
手間は増えますが慣れる為に、
シートを使わず
配列を使うように心がけています。
コメント