[JAVA] 최대공약수, 최소공배수 구하기

알고리즘 문제를 풀다보면 최소공배수를 구하는 문제가 나오지만

최소공배수를 구하기 위해서는 최대공약수가 필요하기에 최대공약수를 먼저 알아보겠습니다.

 

최대공약수

최대공약수란 0이 아닌 정수의 두 개 이상의 정수의 공통되는 약수 중에서 가장 큰 수를 말합니다.

최대공약수를 구하는 방법으로는 소인수분해를 이용하거나 나눗셈을 이용해서 구하는 방법이 있으며 둘 다 소인수 분해 원리를 기반으로 하고있습니다.

그러나 두 정수가 커질 수록 소인수 분해를 하기가 쉽지 않기에 보다 효과적 방법인 나눗셈 정리에 기반을 둔 유클리드 호제법을 사용하는 것입니다.

 

유클리드 호제법이란??

두 정수 X, Y에서 X를 Y로 나눈 나머지 값을 R이라고 합니다. 

R값을 구한 후 다시 Y를 R로 나눈 나머지 값을 구하며 나머지가 0이 될때 까지 반복합니다.

나머지가 0이 나오면 Y에 위치한 값이 두 정수 X, Y의 최대 공약수가 되며 GCD(Greatest Common Divisor)라고 합니다.

즉, X와 Y의 최대 공약수는 Y와 R의 최대공약수가 되는 식이 유클리드 호제법입니다.

 

최소공배수

공배수란 두 정수의 배수 중 공통이 되는 배수를 말합니다.

최소공배수는 공배수 중 가장 작은 수를 말하며 LCM(Least Common Multiple)이라고 합니다.

최소 공배수를 구하기 위해서는 두 정수 X, Y를 곱한 값을 X, Y의 GCD(최대 공약수)로 나누면 됩니다.

- main -

public static void main(String[] args) {    
    int[] a = new int[]{90, 24};
                
    System.out.println("90,24의 최대 공약 수 :"+gcd(a[0],a[1]));
    System.out.println("90,24의 최소 공배 수 :"+lcm(a[0],a[1]));
}

결과 : 
90,24의 최대 공약 수 :6
90,24의 최소 공배 수 :360

 

- 최대 공약수 -

//최대 공약수 - 유클리드 호제법
// 두 수 중 작은값, 두 수를 나눈 나머지를 구한다.
// 작은값%나머지 반복하여 나머지 값이 0이 될때까지 한다.
public static int gcd(int x, int y) {
    int r;
    if(x<y) {
        int temp=x;
        x=y;
        y=temp;
    }
    while(y!=0) {
        r=x%y;
        x=y;
        y=r;
    }
    return x;
}

 

- 최소 공배수 -

//최소 공배수
// 두 수 a*b / 최대공약수 gcd 
public static int lcm(int x, int y) {
    return x*y/gcd(x, y);
}

 

만약 정수가 2개가 아닌 3개 이상의 최대공약수, 최소공배수를 구해야 하는 경우

2개의 정수부터 최대공약수, 최소공배수 값을 구한 후 그 값을 이용해 다시 최대공약수, 최소공배수를 구하면 됩니다.

public static void main(String[] args) {    
    int[] a = new int[]{50, 16, 24};
    int gcd = a[0], lcm = a[0];
    
    for(int i=1;i<a.length;i++) {
        gcd = gcd(gcd,a[i]);
        lcm = lcm(lcm,a[i]);
    }
    System.out.println("50, 16, 24의 최대 공약 수 :"+gcd);
    System.out.println("50, 16, 24의 최소 공배 수 :"+lcm);
}

결과 : 
50, 16, 24의 최대 공약 수 :2
50, 16, 24의 최소 공배 수 :1200