유클리드 호제법

🏷️ 정보

유클리드 호제법(Euclidean algorithm)은 두 수의 최대공약수(GCD, Greatest Common Divisor)를 구하는 효율적인 방법이다. 두 수의 나머지를 반복적으로 구하여 최대공약수를 찾는다. 기본적인 아이디어는 두 수의 최대공약수가 나머지를 구하는 과정에서 점차적으로 줄어든다는 것이다.

유클리드 호제법 알고리즘

  1. 두 수 \(a\)와 \(b\)가 있을 때, \(a\)를 \(b\)로 나눈 나머지를 구한다.
  2. 나머지가 0이면, \(b\)가 \(a\)와 \(b\)의 최대공약수이다.
  3. 나머지가 0이 아니면, \(a\)와 \(b\)를 \(b\)와 나머지로 교체하고 1번부터 반복한다.

최소공배수 (LCM)

두 수의 최소공배수는 그 두 수의 공배수 중 가장 작은 값을 의미한다. 최대공약수를 알고 있다면, 두 수의 최소공배수는 아래와 같이 구할 수 있다.

\[\text{LCM}(a, b) = \frac{|a \times b|}{\text{GCD}(a, b)}\]

즉, 두 수의 곱을 그들의 최대공약수로 나누면 최소공배수를 구할 수 있다.

유클리드 호제법을 이용한 최대공약수 및 최소공배수 구하기

파이썬 코드


<!-- -->
# 유클리드 호제법을 이용한 최대공약수 구하기
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a


<!-- -->
# 최소공배수 구하기 (GCD 활용)
def lcm(a, b):
    return abs(a * b) // gcd(a, b)


<!-- -->
# 예시: 48과 180에 대해 최대공약수와 최소공배수 구하기
a = 48
b = 180

gcd_value = gcd(a, b)
lcm_value = lcm(a, b)

print(f"최대공약수(GCD): {gcd_value}")
print(f"최소공배수(LCM): {lcm_value}")

C 코드

#include <stdio.h>

// 유클리드 호제법을 이용한 최대공약수 구하기
int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// 최소공배수 구하기 (GCD 활용)
int lcm(int a, int b) {
    return (a * b) / gcd(a, b);
}

int main() {
    int a = 48, b = 180;

    int gcd_value = gcd(a, b);
    int lcm_value = lcm(a, b);

    printf("최대공약수(GCD): %d\n", gcd_value);
    printf("최소공배수(LCM): %d\n", lcm_value);

    return 0;
}