1. 유클리드 호제법

A. 정의

• 최대공약수(GCD)와 최소공배수(LCM)을 구하기 위한 알고리즘
• 시간복잡도를 기존 O(N)에서 O(logN)으로 줄일 수 있다.
• 호제법 : 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 방법

ex) 85와 51의 최대 공약수를 유클리드 호제법을 사용하여 구해보자.

X % Y = R이라고 했을 때, X,Y의 최대 공약수는 Y와 R의 최대 공약수와 같다는 특징을 기억하자. 나머지 R이 0이 될 때까지 Y와 R의 나머지 연산을 반복한다.
85 % 51 = 34
51 % 34 = 17
34 % 17 = 0
이때, Y 값의 자리에 있는 17이 최대 공약수가 된다.