
二つの数字の最大公約数を求めたいのですがどうしたらいいのかわからず困っています…。プログラムに関しては初心者なのでどなたか分かりやすく教えてもらえませんか??
<さらにもし出来る方がおられたら…>------------------------------------
実は最終的にはある数(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を探す
今、見られている記事はコレ!
-
釣りと密漁の違いは?知らなかったでは済まされない?事前にできることは?
知らなかったでは済まされないのが法律の世界であるが、全てを知ってから何かをするには少々手間がかかるし、最悪始めることすらできずに終わってしまうこともあり得る。教えてgooでも「釣りと密漁の境目はどこです...
-
カスハラとクレームの違いは?カスハラの法的責任は?企業がとるべき対応は?
東京都が、客からの迷惑行為などを称した「カスタマーハラスメント」、いわゆる「カスハラ」の防止を目的とした条例を、全国で初めて成立させた。条例に罰則はなく、2025年4月1日から施行される。 この動きは自治体...
-
なぜ批判コメントをするの?その心理と向き合い方をカウンセラーにきいた!
今や生活に必要不可欠となったインターネット。手軽に情報を得られるだけでなく、ネットを介したコミュニケーションも一般的となった。それと同時に顕在化しているのが、他者に対する辛らつな意見だ。ネットニュース...
-
大麻の使用罪がなかった理由や法改正での変更点、他国との違いを弁護士が解説
ドイツで2024年4月に大麻が合法化され、その2ヶ月後にサッカーEURO2024が行われた。その際、ドイツ警察は大会運営における治安維持の一つの方針として「アルコールを飲んでいるグループと、大麻を吸っているグループ...
-
ピンとくる人とこない人の違いは?直感を鍛える方法を心理コンサルタントに聞いた!
根拠はないがなんとなくそう感じる……。そんな「直感がした」という経験がある人は少なくないだろう。ただ直感は目には見えず、具体的な説明が難しいこともあるため、その正体は理解しにくい。「教えて!goo」にも「...
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
正しい五十音順について
-
A*アルゴリズム
-
Visual Basicの課題
-
シードを考慮したトーナメント...
-
ハードディスクの処分について...
-
gooという検索エンジンの後にGo...
-
データを圧縮したい
-
c言語で画像から文字を認識 キ...
-
将棋ゲームについて
-
プログラミングについて
-
色(RGB)に少し詳しい方にお願い...
-
迷路プログラム
-
多変数関数の最小値を求めるプ...
-
SEO対策会社ヴォラーレの対応は...
-
簡単なアルゴリズムの添削をお...
-
BCDについて
-
アルファ値を持つ画素同士の合成
-
ルービックキューブの解法プロ...
-
プログラミングの能力とアルゴ...
-
ハッシュアルゴリズム
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
正しい五十音順について
-
[ EXCEL VBA ] 図形を読み込む...
-
BCDについて
-
アルゴリズムとプロトコールの違い
-
期間重複チェックがわかりません
-
グループを均等に分けるには?...
-
多変数関数の最小値を求めるプ...
-
C♯で電卓を作成しています。演...
-
ハノイの塔のさいきアルゴリズ...
-
Officeのラスタ画像の拡大縮小...
-
VB2010にて分数表示(約...
-
ドロネー三角形のプログラム
-
マージソートの比較回数の計算...
-
書籍のソースコードを別言語に...
-
SNSをやらない理由ってなんです...
-
C言語初心者の質問失礼いたしま...
-
バケット法による文字列ソート
-
CRC-CCITT16の算出法
-
黒の塊の数え方
-
六曜の自動計算について
おすすめ情報