
二つの数字の最大公約数を求めたいのですがどうしたらいいのかわからず困っています…。プログラムに関しては初心者なのでどなたか分かりやすく教えてもらえませんか??
<さらにもし出来る方がおられたら…>------------------------------------
実は最終的にはある数(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で質問しましょう!
このQ&Aを見た人はこんなQ&Aも見ています
関連するカテゴリからQ&Aを探す
今、見られている記事はコレ!
-
弁護士が解説!あなたの声を行政に届ける「パブリックコメント」制度のすべて
社会に対する意見や不満、疑問。それを発信する場所は、SNSやブログ、そしてニュースサイトのコメント欄など多岐にわたる。教えて!gooでも「ヤフコメ民について」というタイトルのトピックがあり、この投稿の通り、...
-
弁護士が語る「合法と違法を分けるオンラインカジノのシンプルな線引き」
「お金を賭けたら違法です」ーーこう答えたのは富士見坂法律事務所の井上義之弁護士。オンラインカジノが違法となるかどうかの基準は、このように非常にシンプルである。しかし2025年にはいって、違法賭博事件が相次...
-
釣りと密漁の違いは?知らなかったでは済まされない?事前にできることは?
知らなかったでは済まされないのが法律の世界であるが、全てを知ってから何かをするには少々手間がかかるし、最悪始めることすらできずに終わってしまうこともあり得る。教えてgooでも「釣りと密漁の境目はどこです...
-
カスハラとクレームの違いは?カスハラの法的責任は?企業がとるべき対応は?
東京都が、客からの迷惑行為などを称した「カスタマーハラスメント」、いわゆる「カスハラ」の防止を目的とした条例を、全国で初めて成立させた。条例に罰則はなく、2025年4月1日から施行される。 この動きは自治体...
-
なぜ批判コメントをするの?その心理と向き合い方をカウンセラーにきいた!
今や生活に必要不可欠となったインターネット。手軽に情報を得られるだけでなく、ネットを介したコミュニケーションも一般的となった。それと同時に顕在化しているのが、他者に対する辛らつな意見だ。ネットニュース...
おすすめ情報
このQ&Aを見た人がよく見るQ&A
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
正しい五十音順について
-
C♯で電卓を作成しています。演...
-
Cプログラミング
-
一番近い組み合わせを見つけるには
-
VB2005でRPG
-
グループを均等に分けるには?...
-
トップダウン解析とボトムアッ...
-
[ EXCEL VBA ] 図形を読み込む...
-
Officeのラスタ画像の拡大縮小...
-
アルゴリズムとプロトコールの違い
-
書籍のソースコードを別言語に...
-
VBAで仕様書は書きますか?
-
あるプログラムのコマンドライ...
-
65536は2の何乗なのでしょうか?
-
VBAにてメール作成した際、一部...
-
Excelで4096点以上のFFTの方法
-
C言語について。
-
読み込み中にアクセス違反が発...
-
[Scilab]function内のゼロ割に...
-
0除算して、落ちるプログラムと...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
正しい五十音順について
-
アルゴリズムとプロトコールの違い
-
期間重複チェックがわかりません
-
グループを均等に分けるには?...
-
BCDについて
-
シミュレーテッドアニーリング...
-
[ EXCEL VBA ] 図形を読み込む...
-
関数がどうしても分かりません
-
アルゴリズム フェルナンデス...
-
アルゴリズムについて(ちょい...
-
basicプログラムです。
-
乗換案内の作り方が知りたいです。
-
フローチャート等を説明したHP
-
動画で間違ったこと言っている
-
パスワードつきZIPの暗号化アル...
-
暗号化アルゴリズム
-
5人のテストの点数を入力すると...
-
ハノイの塔のさいきアルゴリズ...
-
ベイチ・カルノー図以外のとき方。
-
gooという検索エンジンの後にGo...
おすすめ情報