유클리드 호제법 (Euclidean Algorithm)

 * 유클리드 호제법 (Euclidean Algorithm)

두 수의 최대공약수를 효율적으로 구하는 알고리즘
수학자 유클리드가 《원론(Elements)》에서 제시한 방법이다

GCD (Greatest Common Divisior) : 최대공약소

LCD (Least Common Multiple) : 최소공배수

mod : 나머지 연산자
a mod b == a%b

a > b에서 a를 b로 나눈 나머지를 r이라고 할 때 (r = a mod b)
gcd(a, b) = gcd(b, r)임을 이용
r = 0일때의 b가 최대공약수이다

gcd(n1, n2) = gcd(n2, n3) = gcd(n3, n4) = ... = gcd(n_last, r)
이렇게 연쇄적으로 이어지고 언젠가 r = 0이 되는 순간이 온다. 그때의 n_last가 최대공약수인 셈

시간복잡도가 O(log(min(a, b)))으로 매우 효율적

재귀와 반복으로 구현 가능

..~~~~..

 * 재귀 gcd()

int gcd(int a, int b)
 if( a == 0)
  return b

 return gcd(b, a%b)

..~~~~..

 * 반복문 gcd()

int gcd(int a, int b)
 while (b != 0)
  int r = a%b
  a = b
  b = r

 return a

..~~~~~..

 * 최소공배수 lcm()

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

..~~~~..

 * 수학에서의 최대공약수와 최소공배수

우선 두 수의 약수를 구한다
그리고 각각 약수와 지수를 정리한다

이때 각 약수들을 최소한으로 지수를 취하고 곱한 것이 최대공약수이고
각 약수들을 최대한으로 지수를 취하고 곱한 것이 최소공배수이다

즉,
최대공약수 : 공통된 소인수의 지수 중 최소값을 취해 곱한 것
최소공배수 : 공통된 소인수의 지수 중 최대값을 취해 곱한 것

..~~~~..