[Algorithm] 최소공배수, 최대공약수와 유클리드 알고리즘 (GCD, LCM)

최대공약수(GCD, Greatest Common Divisor)

최대 공약수란 두 자연수의 공통된 약수 중 가장 큰 수 이다.

두 개 이상의 정수의 최대공약수는 해당 정수들의 공통된 약수 중 가장 큰 값이다.

예를 들어, 8과 12의 최대공약수는 4 이다.

 

최소 공배수(LCM, Least Common Multiple)

최소 공배수란 두 자연수의 공통된 배수 중 가장 작은 수이다.

두 개 이상의 정수의 최소공배수는 주어진 정수들 중에서 모든 정수가 동시에 나누어 떨어지는 가장 작은 정수이다.

예를 들어, 8과 12의 최소공배수는 24이다.

 

유클리드 알고리즘

유클리드 알고리즘은 두 정수의 최대공약수를 구하는데 사용되는 알고리즘이다.

두 정수 a와 b에 대해서, a를 b로 나눈 나머지를 구하고, 그 나머지를 b로 대체하는 과정을 반복하여 나머지가 0이 될 때까지 반복한다.

나머지가 0이 되면 그 때 b가 최대공약수가 됩니다.

 

public class Main {
    
    // 최대공약수 계산
    public static int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }
    
    // 최소공배수 계산
    // 최소공배수는 두 자연수의 곱 / 최대 공약수 라는 공식으로 구할 수 있다.
    public static int lcm(int a, int b) {
        return (a * b) / gcd(a, b);
    }
    
    public static void main(String[] args) {
        int num1 = 8;
        int num2 = 12;
        
        int gcdResult = gcd(num1, num2);
        int lcmResult = lcm(num1, num2);
        
        System.out.println("최대공약수: " + gcdResult);
        System.out.println("최소공배수: " + lcmResult);
    }
}