gcd  最大公約数を算出する

int gcd(int n1, int n2);

n1、n2  2つの負でない整数

2つの整数の最大公約数

int gcd(int n1, int n2)
{
    if (n2 == 0) return n1;
    else return gcd(n2, n1 % n2);
}

Lameの定理により、このアルゴリズムは整数の小さい方の桁数の5倍 以内で必ず終了する。よって計算量は O(logN) である。

また、n個数の最大公約数を求めるには、まず最初2つの整数に上記の 方法を適用して最大公約数を求め、つぎに3つ目の整数と計算した最大 公約数から再び最大公約数を計算する。このように最後の整数まで繰] り返せば、n個の整数の最大公約数が求められる。