
二つの数字の最大公約数を求めたいのですがどうしたらいいのかわからず困っています…。プログラムに関しては初心者なのでどなたか分かりやすく教えてもらえませんか??
<さらにもし出来る方がおられたら…>------------------------------------
実は最終的にはある数(a(素数))があって、そのaと”たがいに素”である数(b)をプログラムで求めたいんです…。
ある本によると適当な二つの素数p、qがあるとしてこのふたつの積(つまりp*q)をmとします。また、(p-1)(q-1)=aとすると ”gcd(b,a)≡1(mod m)” という式を満たすんだそうです…。
※この中にでてくる値で実際に分からないのは"b"のみです。
※ここで書いているgcd(b,a)というのはaとbの最大公約数のことです。
---------------------------------------------------------------------
かなり難しいのでこの質問の回答をいただくと本当に助かります。
よろしくお願いしますm(_ _)m
No.1ベストアンサー
- 回答日時:
はじめまして。
私の持っている本に最大公約数を求めるサンプルマクロが載っておりましたので、お知らせいたします。私も試したところうまく動きましたので、間違えないかと思います。
Sub test()
Dim iNum1 As Integer
Dim iNum2 As Integer
iNum1 = Val(InputBox("整数1は?"))
iNum2 = Val(InputBox("整数2は?"))
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
- 回答日時:
あなたのやりたいことは、このようなことでよろしいのでしょうか。
サンプルマクロを提示します。
Sub test()
Dim iNum(1 To 4) As Integer
Dim i As Integer
iNum(1) = Val(InputBox("整数1は?"))
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
わたしが、エクセル2000のVBAで実行したところ、お互いに素になる数を求めることができました。
kazuhiko5681さん親切に再度ご回答していただいて本当にありがとうございます。
両方の回答を比べつつ私の作るプログラムに適した考え方を使っていこうと思います!!
No.3
- 回答日時:
○プログラムよりアルゴリズムの理解、決定(通常数種あってどれを使うべきか選択)が先です。
本件ユークリッドの互助法の演習とすれば。(あるいはユークリッドの互助法を直接使うなという演習かも)
○書いておられる定理のようなものは、概してコンピュターでは「直接」は使えません。難しすぎます。
○下記で理解してください。下記URLの例の数を使った。
1523=1×814+709
(1523,814)=(814,709)
(a,b)はaとbの公約数を表す記号とします。
理屈は下記に図示説明あり。
http://www.hokuriku.ne.jp/fukiyo/math-obe/euclid …
推移律的に(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)
最大公約数は1です。
右辺の(b、c)のcが0の時は割りきれる訳ですから
bが最大公約数です。
右辺の(b、c)のcが1の時はこれ以上が割り算は続け (て意味なし)られないので1が最大公約数です。
(参考)http://web2.incl.ne.jp/yaoki/ansgcm.htm
-----VBでの初等的解法
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
- 回答日時:
かなりベタですが。
2つの数を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 で順に割ってその余りが0になるのものがa1つだけならば、その数aは素数です。
回答ありがとうございました!!
とても分かりやすく説明していただいたのでちゃんと理解することができました!
これのプログラム化に挑戦してみたいと思います。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- C言語・C++・C# C#の問題で2つの整数a,bの最大公約数(GCD)を求めるユークリッドの互除法は,aをbで割った余り 2 2022/06/26 16:52
- 数学 中一数学の【最大公約数と最小公倍数】の問題です。 1問だけでも教えていただけると嬉しいです。 (1) 4 2022/08/01 10:19
- その他(プログラミング・Web制作) パイソンのプログラミングについての質問です 2 2023/05/22 12:39
- 数学 最小公倍数と最大公約数の求め方で画像のような計算法があったのですが、理解できません。 なぜ2つ数24 4 2022/04/10 13:37
- 大学受験 至急! 数学 整数 なぜ3以上にならないのですか? 3 2023/01/29 12:47
- 数学 ユークリッドの互除法、合同式の問題について 1 2022/05/08 11:49
- 数学 多様体について質問です。 Rを実数全体としてf:S^n={(p_1,…,p_(n+1)∈R^(n+1 2 2023/06/24 00:54
- 数学 正の約数の個数が20個である最小の自然数を求めよ」 という問題で、(□+1)×(△+1)=20となる 4 2022/07/26 11:58
- 大学受験 整数問題 Nを正の整数とする。 N+18がN+2の倍数となるようなNの値の個数を求めたい。 解説に、 1 2022/08/13 12:25
- 国家公務員・地方公務員 公務員試験の数的処理で苦戦しています。 1 2023/01/30 08:56
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
正しい五十音順について
-
[ EXCEL VBA ] 図形を読み込む...
-
CRC-CCITT16の算出法
-
ランダム関数を作りたい。
-
検索エンジンの検索結果の優先...
-
期間重複チェックがわかりません
-
2Dゲームの放物線アルゴリズム...
-
Visual studio2019 C#で生まれ...
-
G4圧縮をTIFに変換アルゴリズム...
-
暗号化・復号化のアルゴリズム...
-
プログラミング能力とアルゴリ...
-
コピー機の拡大法について
-
SEO対策ってなんですか?
-
5人のテストの点数を入力すると...
-
点Qから最短距離の点Piを効率的...
-
OpenCVのライセンスについて
-
迷路プログラム
-
Base64エンコーディングのアル...
-
Nクイーンについて
-
ダイクストラ法の計算量の求め...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
正しい五十音順について
-
[ EXCEL VBA ] 図形を読み込む...
-
BCDについて
-
アルゴリズムとプロトコールの違い
-
期間重複チェックがわかりません
-
グループを均等に分けるには?...
-
多変数関数の最小値を求めるプ...
-
C♯で電卓を作成しています。演...
-
ハノイの塔のさいきアルゴリズ...
-
Officeのラスタ画像の拡大縮小...
-
VB2010にて分数表示(約...
-
ドロネー三角形のプログラム
-
マージソートの比較回数の計算...
-
書籍のソースコードを別言語に...
-
SNSをやらない理由ってなんです...
-
C言語初心者の質問失礼いたしま...
-
バケット法による文字列ソート
-
CRC-CCITT16の算出法
-
黒の塊の数え方
-
六曜の自動計算について
おすすめ情報