java 최대공약수 구하기

두 수의 최대공약수(Greatest Common Divisor, GCD)는 두 수가 공통으로 가지고 있는 가장 큰 약수를 의미합니다. 다시 말해, 주어진 두 수 중에서 더 작은 수로도 나누어떨어지는 가장 큰 수를 말합니다.

최대공약수를 계산하는 방법은 여러 가지가 있습니다. 그 중 가장 일반적인 방법은 "유클리드 호제법"을 사용하는 것입니다. 이 방법은 두 수의 차이가 두 수 중 작은 수로 나누어떨어질 때까지 두 수를 계속 나누어주는 과정을 반복하여 최대공약수를 찾는 방법입니다.

예를 들어, 30과 45의 최대공약수를 구하는 경우:

45를 30으로 나누면 나머지가 15가 남습니다. (45 ÷ 30 = 1, 나머지 15)
이제 30을 15로 나누면 나머지가 0이 됩니다. (30 ÷ 15 = 2, 나머지 0)
나머지가 0이 되었을 때의 나누는 수, 즉 15가 두 수 30과 45의 최대공약수입니다.

자바에서는 gcd 메서드를 사용하여 두 수의 최대공약수를 계산할 수 있습니다. 아래는 유클리드 호제법을 사용한 최대공약수 계산 코드 예시입니다:

아래 코드에서 gcd 함수는 두 수의 최대공약수를 계산하는 역할을 합니다. 입력된 두 수의 최대공약수를 구하여 반환하게 됩니다.

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

    public static void main(String[] args) {
        int num1 = 30;
        int num2 = 45;
        int result = gcd(num1, num2);
        System.out.println("최대공약수: " + result);  // 출력: 최대공약수: 15
    }
}