[알고리즘] 유클리드 호제법

유클리드 알고리즘은 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 나타낸다.

유클리드 호제법은 나눗셈만 반복해서 최대공약수를 구할 수 있다.
두 개의 수가 아무리 커도 정해진 순서로 계산하면 효율적으로 최대공약수를 구할 수 있다.

유클리드 호제법은 반복문과 재귀함수를 통해 쉽게 표현할 수 있다.

최대공약수

반복문

a > b임을 가정

// b가 0이 될때까지(a%b), 반복문을 돌게되고,
// b가 0인 순간의 a를 GCD로 판단하고 리턴합니다.
int GCD(int a, int b){
  while(b != 0){
    int r = a % b;
    a = b;
    b = c;
  }
  return a;
}

재귀함수

int GCD(int a, int b){
  return b ? GCD(b, a % b) : a;
}

최소공배수

int LCM(int a, int b){
  return a * b / GCD(a, b);
}