[JAVA] 유클리드 호제법 - 최대 공약수, 최대 공배수

유클리드 호제법

- 두 다항식의 최대 공약수를 구하는 방법

- 두 양의 정수 a,b(a>b)에 대하여 a = bq + r (0<=r<=b)이면, a,b의 최대 공약수는 b,r의 최대 공약수와 같다.

 

최대 공약수 : 두 자연수의 공통된 약수 중 가장 큰 수

최대 공배수 : 두 자연수의 공통된 배수 중 가장 작은 수

 

최대 공약수(GCD) 최대 공배수(LCM) 코드

- while문으로 b가 0이 될때까지 a%b=c

ex. a=72, b=30

GCD(72,30) // 72%30 = 12

-> (b->a, c->b으로 변경해준다.)

-> GCD(30, 12) = 30%12 = 6

-> GCD(12,6) = 0

-> b인 6이 72와 30의 최대 공약수가 된다.

 

최대 공배수 = 두 수의 곱 / 두 수의 최대공약수

= a * b / GCD(a,b)

ex. GCD(72,30) 에서 최대공약수는 6 이다.

-> 72*30 / 6 = 360

72와 30의 최대 공배수는 360

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

        answer[0] = GCD(n,m);
        answer[1] = lcm(n,m);
        return answer;
    }

    public static int GCD(int a, int b){ // 최대 공약수
        while(b!=0){
            int c = a%b;
            a=b;
            b=c;
        }
        return a;
    }

    public static int lcm(int a, int b){ // 최대 공배수
        return a*b / GCD(a,b);
    }
}