C++ | ユークリッド互除法で最大公約数を求める

整数アルゴリズムの伝統的なものに、ユークリッド互除法があります。
2つの整数をインプットとし、これらの最大公約数を求めるものです。

再帰アルゴリズムのサンプルとしても、よく参照されます。

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
  • URLをコピーしました!
  • URLをコピーしました!

コメント

コメントする

このサイトは reCAPTCHA と Google によって保護されていますプライバシーポリシー利用規約 申し込み。

The reCAPTCHA verification period has expired. Please reload the page.

目次