유클리드 호제법

Euclidean algorithm

자연수 2개의 최대공약수(greatest common diviser)를 구하는 알고리즘이다. 입력받은 두 수를 서로(互) 나누기(除) 때문에 호제법(互除法) 이라는 이름으로 불린다. 두 개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라고 하면, a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질을 이용해 r이 0이 될 때 까지 반복해서 나누었을 때의 나누는 수가 a와 b의 최대공약수 라고 한다.

C++

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

// 최소공배수 (least common multiple)
int lcm(int a, int b){
    return a * b / gcd(a, b);
}