재귀함수를 이용한 유클리드 호제법(최대 공약수)

유클리드 호제법

두 양의 정수의 최대공약수를 찾는 효율적인 방법

 

유클리드 호제법의 두가지 방법

• 뺄셈을 이용 : 두 수 중 큰 수에서 가장 작은 수를 뺀다. 이 과정을 두 수가 같아질 때까지 반복한다. 최종적으로 남은 수가 두 수의 최대공약수이다.
• 나눗셈을 이용 : 두 수 a와 b(a > b)가 있을 때, a를 b로 나눈 나머지를 구한다. 그 다음 b와 이 나머지의 최대공약수를 구한다. 이 과정을 나머지가 0이 될 때까지 반복한다.

<재귀함수를 이용한 유클리드 호제법(나눗셈 이용)>

import java.util.Scanner;

class GCDCalculator {
    //--- 두 정수 x와 y의 최대공약수(GCD)를 재귀적으로 계산합니다 ---//
    static int calculateGCD(int x, int y) {
        if (y == 0)
            return x; // 기저 조건: y가 0이면 x가 최대공약수
        else
            return calculateGCD(y, x % y); // 유클리드 호제법을 사용한 재귀 호출
    }

    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);
        System.out.println("두 수의 최대공약수를 계산합니다.");
        System.out.print("첫 번째 정수를 입력하세요: ");
        int x = stdIn.nextInt();
        System.out.print("두 번째 정수를 입력하세요: ");
        int y = stdIn.nextInt();
        System.out.println("두 수의 최대공약수는 " + calculateGCD(x, y) + "입니다.");
        System.out.println(calculateGCD2(x, y));
    }
}