[자료구조 및 알고리즘] 유클리드 호제법

유클리드 호제법

def gcd(a,b):
  while b: # b가 0이 아닐때까지
    a,b = b, a%b # a는 나누는 값을 할당하고 b는 a와 b를 나누었을 때 나머지를 할당
  return a # 최대공약수

int gcd(int x, int y) {
  while (y) {
    int temp = x%y;
    x = y;
    y = temp;
  }
  return x;
}

 

 

유클리드 호제법은 최대공약수를 구할 때 사용하는 알고리즘이다. 증명은 어려우므로 다른 블로그를 참고하는 게 좋을 것 같다. 최소공배수는 두 수를 곱한 뒤 최대공약수로 나누면 구할 수 있다.

https://roytravel.tistory.com/43

유클리드 호제법 증명