최소공배수 / 유클리디안 호제법

최소공배수

---

알고리즘을 공부하다 보면 최소공배수를 구하는 경우가 존재 합니다.

이 때 사용할 수 있는 최소공배수 알고리즘에 대해 알아보겠습니다.

최소공배수를 구하는 방법에는 대표적으로 유클리디안 호제법이 있습니다.

최소공배수를 구하고 싶은 a와 b라는 숫자가 있다고 가정하겠습니다.

case 1

가장 좌측에는 몫이 존재하며 우측에는 모듈러의 값이 존재합니다.

만약 두 수의 최대공약수가 존재한다면 위의 연산을 반복하였을 시 b가 0이되는 순간이 존재합니다.

그 때의 a가 두 수의 최대공약수가 됩니다.

case 2

만약 두 수가 서로소라면, 즉 최대공약수가 1이라면 b가 0이 되는 순간 a가 1이 된다.

따라서 최대공약수가 1임을 알 수 있다.

소스코드는 위와 같으며 출력창은 다음과 같습니다.