[Java] 최대공약수, 최소공배수 구하기(유클리드 호제법)

유클리드 호제법

2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘의 하나이다.

호제법이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 나타낸다.

1. 두 수 중 큰 수를 작은 수로 나누어 나머지를 구한다.

2. 작은 수를 방금 구한 나머지로 나눈다.

3. 나머지가 0이 될 때까지 반복한다.

4. 나머지가 0이 될 때 나눴던 수가 최대공약수이다.

 

최대공약수를 구하는 코드

private int gcd(int max, int min) {
    while (max % min != 0) {
    	int temp = max;
        max = min;
        min = temp % min;
    }
    return min;
}

//아래와 같이 재귀 함수로 간단하게 나타낼 수도 있다.
private int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

 

최소공배수

private int lcm(int a, int b) {
    //최소공배수 = a*b/최대공약수
    return a * b / gcd(a, b);
}

private int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}