ユークリッドの互除法

ユークリッドの互除法

ユークリッドの互除法を用いて、２つの整数の最大公約数を出力する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 << "２つの整数を入力してください";
  cin >> a >> b;
  c = gcd(a, b);
  cout << "最大公約数は" << c <<"です\n";
  return 0;
}

実行結果

まとめ

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

参考

独習C++ 第4版