유클리드 호제법 (최대공약수)

문제 풀다가 유클리드 호제법이 나왔다.

옛날에 정리해 놓은 줄 알았는데 없어서 정리.

 

유클리드 호제법 (Greatest Common Divisor) : 최대공약수 구함

gcd(a,b) = gcd(b, a%b)가 성립

 

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

 

int gcd(int a, int b)
{
    int c;
    while(b != 0)
    {
        c = a % b;
        a = b;
        b = c;
    }
    return a;
}

a와 b의 최대공약수를 리턴한다.

 

 

 

최소공배수 (Least Common muliple)

 

최소공배수는 다음이 성립한다 

 

a * b = lcm(a, b) * gcd(a, b)

 

즉 lcm(a, b) = (a * b) / gcd(a, b) 이므로 

 

a와 b의 곱한 값에 최대공약수를 나눠주면 된다.