数学のユークリッドアルゴリズム(一)

ユークリッドアルゴリズムは転々相除法とも呼ばれ、最大公約数を解くアルゴリズムです.
定理:ユークリッドアルゴリズムの理論的支持はGCD再帰定理であり、以下にこの定理を紹介する.GCD再帰定理:任意の負の整数aと任意の正の整数bに対して、gcd(a,b)=gcd(b,a%b)
コード:上記の定理により、gcd関数のコードを直接導出できます.

int gcd(int a,int b){
    return b==0?a:gcd(b,a%b);
}

拡張:a,bの最大公約数により、a,bの最小公倍数を求めることができます.lcm関数:

int lcm(int a,int b){
    return a/gcd(a,b)*b;
}