유클리드 호제법을 이용한 최대 공약수

(a,b) = a와 b의 최대공약수
a = b * q + r일 때, (a,b) = (b, r) = (b, a%b)이다.
r이 0이 될 때의, b의 값이 최대 공약수이다.

ex) (1980, 168) = (168, 132) = (132, 36) = (36, 24) = (24, 12) = (12, 0)
r이 0이 될 때의 b의 값은 12이므로, (1980, 168)은 12이다.

재귀로 풀기

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

유클리드 호제법에서 인자 a와 b의 크기는 중요햐지 않다!(그냥 넣으면 알아서 뒤집어주기 때문에)
a < b라면, % 연산에 의해 a > b로 뒤집어진다.
따라서 굳이 a > b로 만들기 위해서 부가적인 연산을 할 필요가 없다!

ex) a = 123, b = 333
(123,333) = (333, 123) = (123, 87) = ...

반복문으로 풀기

public int gcd(int a, int b){
    while(true){
       int r = a%b;
       if(r==0) return b;

       a = b;
       b = r;
    }
}

-> 단, a > b인 조건에서만 사용 가능

시간 복잡도

유클리드 호제법을 사용하지 않고 최대 공약수를 구하면, O(N)이다.
(a, b 중 작은 값을 min이라고 할 때, 1~min까지 for문을 돌려 확인해야 하므로)

유클리드 호제법을 사용하면, 시간복잡도는 O(log N)이다.
% 연산자를 사용하여, 값을 크게 줄여나가는 방식을 사용하기 때문에

=> 시간 복잡도를 O(log N)으로 줄일 수 있으므로, 효율적이다.

유클리드 호제법을 이용한 최소 공배수

int lcm(int a, int b){
    return a * b / gcd(a,b);
}

최소 공배수는 gcd * (a/gcd) * (b/gcd) = a * b / gcd이다.

---

[참고]
https://www.youtube.com/watch?v=TxdljAFjTNw
https://coding-factory.tistory.com/599