最大公約数を求めたい！

質問

二つの数字の最大公約数を求めたいのですがどうしたらいいのかわからず困っています…。プログラムに関しては初心者なのでどなたか分かりやすく教えてもらえませんか？？

＜さらにもし出来る方がおられたら…＞------------------------------------
実は最終的にはある数（a（素数））があって、そのaと”たがいに素”である数（ｂ）をプログラムで求めたいんです…。

ある本によると適当な二つの素数ｐ、ｑがあるとしてこのふたつの積（つまりｐ＊ｑ）をｍとします。また、(p-1)(q-1)＝aとすると ”gcd(b,a)≡1(mod m)” という式を満たすんだそうです…。

※この中にでてくる値で実際に分からないのは"b"のみです。
※ここで書いているgcd(b,a)というのはaとｂの最大公約数のことです。
---------------------------------------------------------------------

かなり難しいのでこの質問の回答をいただくと本当に助かります。
よろしくお願いしますm(_ _)m

回答No.1

kazuhiko5681 · ベストアンサー

はじめまして。
私の持っている本に最大公約数を求めるサンプルマクロが載っておりましたので、お知らせいたします。私も試したところうまく動きましたので、間違えないかと思います。

Sub test()

Dim iNum1 As Integer
Dim iNum2 As Integer

iNum1 = Val(InputBox("整数１は？"))
iNum2 = Val(InputBox("整数２は？"))

Do Until iNum1 = iNum2
If iNum1 > iNum2 Then
iNum1 = iNum1 - iNum2
Else
iNum2 = iNum2 - iNum1
End If
Loop

MsgBox Str(iNum1)

End

End Sub

お礼

サンプルマクロありがとうございました！
これなら代入する値を変えてそのままつかえそうですね(^^)
試してみます！

回答No.4

kazuhiko5681

あなたのやりたいことは、このようなことでよろしいのでしょうか。
サンプルマクロを提示します。

Sub test()

Dim iNum(1 To 4) As Integer
Dim i As Integer

iNum(1) = Val(InputBox("整数１は？"))

For i = 1 To iNum(1) - 1
iNum(2) = iNum(1)
iNum(3) = iNum(1) - i
iNum(4) = iNum(3)

Do Until iNum(2) = iNum(4)
If iNum(2) > iNum(4) Then
iNum(2) = iNum(2) - iNum(4)
Else
iNum(4) = iNum(4) - iNum(2)
End If
Loop

If iNum(2) = 1 And iNum(3) > 1 Then
MsgBox iNum(3)
End If
Next i

End Sub

わたしが、エクセル２０００のＶＢＡで実行したところ、お互いに素になる数を求めることができました。

お礼

kazuhiko5681さん親切に再度ご回答していただいて本当にありがとうございます。

両方の回答を比べつつ私の作るプログラムに適した考え方を使っていこうと思います！！

回答No.3

imogasi

○プログラムよりアルゴリズムの理解、決定（通常数種あってどれを使うべきか選択）が先です。本件ユークリッドの互助法の演習とすれば。
（あるいはユークリッドの互助法を直接使うなという演習かも）
○書いておられる定理のようなものは、概してコンピュターでは「直接」は使えません。難しすぎます。
○下記で理解してください。下記ＵＲＬの例の数を使った。
　　1523=1×814+709
(1523,814)=(814,709)
(a,b)はaとbの公約数を表す記号とします。
　　理屈は下記に図示説明あり。
　http://www.hokuriku.ne.jp/fukiyo/math-obe/euclid.htm
　　推移律的に(a,b)=(b,c)のcはbより小さくなります。
814=1×709+105
(814,709)=(709,105)
709=6×105+79
(709,105)=(105,79)
105=1×79+26
(105,79)=(79,26)
79=3×26+1
(79,26)=(26,1)
最大公約数は１です。
　　右辺の（ｂ、ｃ）のｃが０の時は割りきれる訳ですから
　　ｂが最大公約数です。
　　右辺の（ｂ、ｃ）のｃが１の時はこれ以上が割り算は続け　（て意味なし）られないので１が最大公約数です。
（参考）http://web2.incl.ne.jp/yaoki/ansgcm.htm
-----ＶＢでの初等的解法
Sub gcd01()
Dim a, b, gcd As Integer
a = InputBox("a=")
b = InputBox("b=(a>b)")
'----
p01:
c = a Mod b
MsgBox "(" & a & "," & b & ")=(" & b & "," & c & ")"
If c = 0 Then
gcd = b
GoTo p02:
End If
If c = 1 Then
gcd = 1
GoTo p02
End If
a = b
b = c
GoTo p01
'----
p02:
MsgBox "gcd=" & gcd
End Sub
バグが無いことを祈りつつ。

お礼

細かい説明を加えた回答ありがとうございました。

実際にVBで実行してみたところ、ちゃんと最終的に最大公約数を求めることができました！のせていただいたURLも参考にしたいと思います。

回答No.2

hinebot

かなりベタですが。
２つの数をa,bとします。
aをa,a-1,a-2,…,2　で順に割ってその余りをチェックします。余りが0であればそのとき割った数を覚えておきます。
（"順に割って"というのは、a/a, a/(a-1),a/(a-2),…　という意味です）
同様のことをbについても行います。
aについて余りが0であった数とbについて余りが0であった数を比較し、共通なものをみつけ、その中で最大のものが最大公約数になります。

※このアルゴリズムだとa,bが大きな数字の場合、かなり時間がかかりそうですが。

なお、aをa,a-1,a-2,…,2　で順に割ってその余りが０になるのものがa１つだけならば、その数aは素数です。

お礼

回答ありがとうございました！！

とても分かりやすく説明していただいたのでちゃんと理解することができました！
これのプログラム化に挑戦してみたいと思います。