[Java] 유클리드 호제법이란?

1️⃣최대공약수 GCD(Greatest Common Divisor)

두 자연수가 공통으로 갖는 약수들 중에서 가장 큰 값

ex) 24와 18의 최대공약수는 6

 

2️⃣최소공배수 LCM(Least Common Multiple)

두 자연수들의 배수들 중에서 공통된 가장 작은수

ex) 24와 18의 최소공배수는 72

 

3️⃣유클리드 호제법 (Euclidean Algorithm)

유클리드 알고리즘은 2개의 자연수의 최대공약수를 구하는 알고리즘

호제법이란 두 수가 서로 상대방 수를 나누어서 결과 값을 얻어내는 알고리즘을 나타낸다.

 

 

2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면( a%b=r 단, a>b)

 

a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

 

이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여
나머지가 0이 되었을 때나누는 수가 a와 b의 최대공약수이다.

---

✏️사용 예시

 

a=24, b=18 이라면

	GCD	a	b	r (a%b)
1	GCD(24, 18)	24	18	6
2	GCD(18, 6)	18	6	0

 

2번째 시도만에 나머지가 0으로 떨어졌으며, 이때 나누는 수(6)가 최대공약수가 된다.

 

 

최소공배수는 최대공약수를 통하여 바로구할 수 있다.

최소공배수 = 두 자연수의 곱 / 최대공약수

 

따라서 24 * 18 / 6 을 계산하여 나온 72가 최소공배수가 된다.

---

💡Java 코드로 적용해보기

class Solution {
    public int[] solution(int n, int m) {

        // 유클리드 호제법을 사용하여 최대공약수와 최소공배수를 구하는 방법
        int a = Math.max(n, m);
        int b = Math.min(n, m);

        while (b > 0) {
            int temp = a % b;
            a = b;
            b = temp;
        }

        int gcd = a; // 최대공약수 greatest common divisor
        int lcm = n * m / gcd; // 최소공배수 least common multiple

        return new int[]{gcd, lcm};
    }
}