最大公約数を見つけたい

質問

C++初心者です。Visual studio 2005を用いてvisual C++の計算フォームアプリケーションを作りたいのです。

２ヶ所のテキストボックスに整数を入力させ、「実行」ボタンを押すとその２つの整数の最大公約数を出力させたいのですが、どうも上手くいきません。

できるだけ簡素なコードで最大公約数を見つけるにはどうすればいいでしょうか？
どうかよろしくお願いいたします。

回答No.7

Werner · ベストアンサー

> 今のコンピュータは充分に高速なので、当方のような「両方で割り切れる数字を、大きい方から順に探して行く」と言うような強引な方法で構わない。
数倍とか数十倍遅い程度ならそういう考え方もありだと思うけど、
アルゴリズムの選択はうっかり間違えると
簡単に計算量が数桁(下手するともっと)変わるから
あまり無頓着になりすぎるのもどうかと思う。

[テストコード]
#include <stdio.h>
#include <time.h>

int gcd1(int m,int n){ //qa2549304より
　int temp;
　if(m<n){
　　temp=m;
　　m=n;
　　n=temp;
　}
　if(n<=0){return m;}
　while(1){
　　temp = m%n;
　　if(temp==0){return n;}
　　m=n;
　　n=temp;
　}
}

int gcd2(int a, int b)
{
　int i;
　for (i=(a<b?a:b);i>=1;i--) {
　　if (!(a%i)&&!(b%i)) {
　　　break;
　　}
　}
　return i;
}

int main(void){
　int a, b, result;
　clock_t t1, t2;

　a = 26565648;
　b = 42544455;

　t1 = clock();
　result = gcd1(a,b);
　t2 = clock();
　printf("gcd1(%d, %d) = %d, time = %10.3f\n", a, b, result, (double)(t2 - t1)/(double)CLOCKS_PER_SEC);

　t1 = clock();
　result = gcd2(a,b);
　t2 = clock();
　printf("gcd2(%d, %d) = %d, time = %10.3f\n", a, b, result, (double)(t2 - t1)/(double)CLOCKS_PER_SEC);

　a = 1000000001;
　b = 1000000000;

　t1 = clock();
　result = gcd1(a,b);
　t2 = clock();
　printf("gcd1(%d, %d) = %d, time = %10.3f\n", a, b, result, (double)(t2 - t1)/(double)CLOCKS_PER_SEC);

　t1 = clock();
　result = gcd2(a,b);
　t2 = clock();
　printf("gcd2(%d, %d) = %d, time = %10.3f\n", a, b, result, (double)(t2 - t1)/(double)CLOCKS_PER_SEC);

　return 0;
}

[出力]
gcd1(26565648, 42544455) = 3, time = 0.000
gcd2(26565648, 42544455) = 3, time = 0.136
gcd1(1000000001, 1000000000) = 1, time = 0.000
gcd2(1000000001, 1000000000) = 1, time = 3.206

回答No.9

psychesine

alpha　>= beta として

//Euclidean algorithm
int gcd(int alpha, int beta)
{
int residue;

while (residue != 0) {
residue = alpha % beta;
alpha = beta;
beta = residue;
}
return alpha;
}

でわかりやすくて良いと思います。

回答No.8

Tacosan

今更だけど, 最大公約数を求めるプログラムを作るのに因数分解するやつはたぶんバカだと思う＞#6. 因数分解が NP-hard であることそのものは証明されてないけど, わざわざ問題を難しくする意味はない.

回答No.6

chie65536

と言う訳で、他の回答のように色々な方法があるけども、今のコンピュータは充分に高速なので、当方のような「両方で割り切れる数字を、大きい方から順に探して行く」と言うような強引な方法で構わない。

互除法とか因数分解とかは「計算量を減らさないと、答えが出るまで死ぬほど時間がかかる大昔の計算機を使う時」に使えば良い。

回答No.5

chie65536

if (((a/i)*i==a)&&((b/i)*i==b)) {
より
　　if (!(a%i)&&!(b%i)) {
の方が早いか。

回答No.4

asuncion

ユークリッドの互除法
について調べてみるとよいかもしれません。

回答No.3

chie65536

#include<stdio.h>
void main(void)
{
　int a,b;
　int i;
　scanf("%d",&a);
　scanf("%d",&b);
　for (i=(a<b?a:b);i>=1;i--) {
　　if (((a/i)*i==a)&&((b/i)*i==b)) {
　　　break;
　　}
　}
　printf("%d\n",i);
}

回答No.2

D-Matsu

素因数分解して、一致する素因数の積を求めればいいんではないでしょうか。

たとえば30と24なら
30 = 2 x 3 x 5
24 = 2 x 2 x 2 x 3
2と3が一つずつ一致するので
2 x 3 = 6 が最大公約数

てな感じで。

回答No.1

DIooggooID

こちらのような方法で、各値の素因数分解を行い、その結果どおしで、マッチングすれば良いと思います。

http://www.sm.rim.or.jp/~shishido/insuu.html