整数アルゴリズムの伝統的なものに、ユークリッド互除法があります。
２つの整数をインプットとし、これらの最大公約数を求めるものです。
あわせて読みたい
再帰アルゴリズムのサンプルとしても、よく参照されます。
C++ でのサンプルコードを掲載します。
#include <iostream>
#include <utility>
unsigned long gcd(unsigned long a, unsigned long b)
{
std::cout << "a: " << a << ", b: " << b << std::endl;
if (a < b)
{
std::swap(a, b);
}
if (b == 0)
{
return a;
}
auto r = a % b;
return gcd(b, r);
}
int main()
{
auto v = gcd(1071, 1029);
std::cout << "最大公約数は " << v << std::endl;
return 0;
}以下は実行例です。
$ g++ gcd.cc && ./a.out
a: 1071, b: 1029
a: 1029, b: 42
a: 42, b: 21
a: 21, b: 0
最大公約数は 21
コメント