유클리드 호제법(Euclidean Algorithm)

유클리드 알고리즘과 호제법

☞  유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다.

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

---

최대공약수(GCD: Greatest Common Divisor) & 최소공배수(LCM: Least Common Multiple)란?

☞ 최대공약수(GCD: Greatest Common Divisor)
: 두 수의 공통된 '약수 중에서 가장 큰 수'를 의미한다.

☞ 최소공배수(LCM: Least Common Multiple)
: 두 수의 공통된 '배수 중에서 가장 작은 수'를 의미한다.

---

두 수의 최대공약수, 최소공배수 구하기

최대공약수(GCD) 구현 방법

1. 반복문으로 구현

b가 0이 될 때까지, a를 b로 나눈 나머지를 b에 대입하고, a와 b의 값을 교환한다.

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

 

2. 재귀함수로 구현

b가 0이라면 a가 최대공약수가 되며, 그렇지 않으면 b와 a % b의 최대공약수를 구한다.

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

 

최소공배수(LCM) 구현 방법

최소 공배수는 두 수의 곱에 최대 공약수를 나눈 값과 같다.

public static int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

---

N개의 수의 최대공약수, 최소공배수 구하기

최대공약수(GCD)

배열을 순회하면서 배열에 있는 모든 수의 최대공약수를 구한다.

public static int gcd(int[] arr) {
    int result = arr[0];
    for (int i = 1; i < arr.length; i++) {
        result = gcd(result, arr[i]);
    }
    return result;
}

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

최소공배수(LCM)

배열을 순회하면서 배열에 있는 모든 수의 최소공배수를 구한다.

public static int lcm(int[] arr) {
    int result = arr[0];
    for (int i = 1; i < arr.length; i++) {
        result = lcm(result, arr[i]);
    }
    return result;
}

public static int lcm(int a, int b) {
    return (a * b) / gcd(a, b);
}

---

참고

https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

유클리드 호제법 - 위키백과, 우리 모두의 백과사전