[알고리즘/JAVA] 최대공약수(GCD) 구하기 - 유클리드 호제법 (+최소공배수(LCM) 구하기)

이미지 출처 나무위키

음.. 위에는 뭐라는지 모르겠고 바로 정리해보도록 하겠습니다.

 

 

 

유클리드 호제법(Euclidean algorithm)

두 수 a와 b의 최대공약수를 구할 때, a를 b로 나눈 나머지를 구하고, 그 나머지와 b로 다시 최대공약수를 구하는 과정을 반복하여 나머지가 0이 될 때의 b 값을 최대공약수로 취하는 방법

(그냥 최대공약수 구하는 알고리즘이구나! 생각하시면 됩니다 ㅎ.ㅎㅎㅎㅎ)

 

 

 

최대공약수(GCD) 구하기

예시 1)

public class MathUtil {
    public static int gcd(int a, int b) {
        while (b != 0) {
            int temp = a % b;
            a = b;
            b = temp;
        }
        return a;
    }
}

• 위 코드에서 gcd 함수는 a와 b를 인수로 받아 최대공약수를 반환함
• while 루프를 통해 b가 0이 될 때까지 나머지를 계속 구하고, 그 때의 a가 최대공약수가 됨

 

 

예시 2) 재귀함수로 GCD 구하기

public class MathUtil {
    public static int gcdRecursive(int a, int b) {
        if (b == 0) {
            return a;
        }
        
        return gcdRecursive(b, a % b);
    }
}

• gcdRecursive 함수는 b가 0인지 확인함
• b가 0이면 a가 최대공약수이므로 a를 반환함
• 그렇지 않다면 gcdRecursive(b, a%b)를 호출하여 계속 재귀적으로 계산

 

 

 

최소공배수(LCM) 구하기

예시 1)

public class MathUtil {
    public static int lcm(int a, int b) {
        return Math.abs(a * b) / gcd(a, b);
    }
}

• 두 수 a와 b를 곱하고 a와 b의 최대공약수(GCD)로 나누면 최소공배수를 구할 수 있음

 

 

최대공약수와 최소공배수 구하기 예시

public class Main {
    public static void main(String[] args) {
        int num1 = 18;
        int num2 = 24;
        
        int gcdRes = MathUtil.gcd(num1, num2);
        int lcmRes = MathUtil.lcm(num1, num2);
        
        System.out.println("GCD : " + gcdRes); // GCD : 6
        System.out.println("LCM : " + lcmRes); // LCM : 72
    }
}