みんなの「教えて(疑問・質問)」にみんなで「答える」Q&Aコミュニティ

こんにちはゲストさん。会員登録(無料)して質問・回答してみよう!

解決済みの質問

最大公約数を見つけたい

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

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

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

投稿日時 - 2008-11-13 13:10:36

QNo.4475237

すぐに回答ほしいです

質問者が選んだベストアンサー

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


[テストコード]
#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

投稿日時 - 2008-11-13 19:07:57

ANo.7

このQ&Aは役に立ちましたか?

2人が「このQ&Aが役に立った」と投票しています

回答(9)

ANo.9

alpha >= beta として

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

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

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

投稿日時 - 2008-11-28 12:31:04

ANo.8

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

投稿日時 - 2008-11-17 17:47:08

ANo.6

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

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

投稿日時 - 2008-11-13 13:41:58

ANo.5

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

投稿日時 - 2008-11-13 13:33:20

ANo.4

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

投稿日時 - 2008-11-13 13:28:03

ANo.3

#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);
}

投稿日時 - 2008-11-13 13:26:49

ANo.2

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

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

てな感じで。

投稿日時 - 2008-11-13 13:23:55

ANo.1

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

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

投稿日時 - 2008-11-13 13:22:47

あなたにオススメの質問