βshortの自堕落Diary

web関係や、プログラミングなどを扱う予定です。プランなど立てていないので、不定期投稿になります。

ユークリッドの互除法

ユークリッドの互除法

ユークリッドの互除法を用いて、2つの整数の最大公約数を出力するC++のコードを作成する。
環境は、Xcodeである。
前回のコンソール入出力の利用です。


ソースコード

#include <iostream>
using namespace std;

int gcd(int a, int b)
{
  if(!b) return a;
  return gcd(b, a%b);
}

int main()
{
  int a , b , c;
  cout << "2つの整数を入力してください";
  cin >> a >> b;
  c = gcd(a, b);
  cout << "最大公約数は" << c <<"です\n";
  return 0;
}

実行結果

f:id:weblog2016it:20170713002833p:plain

まとめ

ユークリッドの互除法の関数gcd()を作成した。
再帰的にすることで、簡略化することができる。

参考


独習C++ 第4版