유클리드 호제법이란?

💫유클리드 호제법

두 수의 최대공약수를 구하는 알고리즘이다.

큰 수를 작은 수로 mod 연산 하는 것이다.
1. 큰 수를 작은 수로 mod연산한다.
2. 작은 수를 나머지와 mod연산한다. (반복)
3. 나머지가 0이 되면 나누는 수가 최대공약수가 된다.

예를 들어, 24와 18의 최대공약수를 구해보자.
24 mod 18 = 6
18 mod 6 = 0
나머지가 0이 되었고, 이 때 6이 바로 최대공약수가 되는 것이다.

여기서
18 mod 24로 시작하는건 안될까??
된다.
어차피 18 mod 24 = 18이고
다음으로 24 mod 18을 수행하게 되니
어차피 결과는 같다.

💚 두 수의 곱 = 최대공약수 x 최소공배수

최대공약수를 구했으면 최소공배수를 구하는건 쉽다.
두 수의 곱 / 최대공약수 로 구할 수 있다.