[최대공약수] 유클리드 호제법

Q. 두 수의 최대공약수와 최소공배수를 구하여라.

1. 최대공약수 구하는 법

유클리드 호제법 (유클리드 알고리즘) 이론

A와 B라는 값의 최대 공약수를 구하고 싶다 가정 (단, A > B)
이때 A를 B로 나눈다고 가정하면, 
A = B * Q + R이다.

최대 공약수를 G라고 하였을 때 아래와 같이 수식을 나타낼 수 있다. (a * G == A, b * G == B) 
a * G = b * G * Q + R

위 수식을 R의 입장으로 정리해보자 R = G * (a - b * Q)

즉, R도 최대 공약수 G를 약수로 갖게 되니 B와 R의 최대 공약수와 A와 B의 최대 공약수는 동일하다.

 

유클리드 호제법 정리 

1. 큰 수를 작은 수로 나눈다.

2. 나누는 수를 나머지로 계속 나눈다.

3. 나머지가 0이 나오면 나누는 수가 최대공약수이다.

 

2. 최소공배수 구하는 법

A*B / (최대공약수)

---

3. 관련 코드

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int [2];
        int c = 0;
        int x = n*m;

        if (n < m) {
            int tmp = n;
            n = m;
            m = tmp;
        }

        while(m!=0){
            c = n%m;
            n = m;
            m = c;
        }

        answer[0] = n; //최대공약수
        answer[1] = x/n; //최소공배수

        return answer;
    }
}