최대공약수와 최소공배수를 손쉽게 구하는 방법과 함께 알아보자.

1. 최대공약수와 최소공배수의 개념

최대공약수와 최소공배수는 두 개 이상의 수에 대해 자주 사용되는 개념이다.

최대공약수 (GCD, Greatest Common Divisor)

최대공약수는 주어진 수들 사이에서 공통으로 나누어떨어지는 가장 큰 수이다. 간단히 말하면 두 수의 공약수 중에서 가장 큰 수를 의미한다. 최대공약수는 주어진 수들을 분수 형태로 표현할 때, 각 항목들의 분모를 최소화하여 표현하는데 유용하게 사용된다.

최소공배수 (LCM, Least Common Multiple)

최소공배수는 두 개 이상의 수들 중 모든 수들을 나누어떨어지게 하는 가장 작은 수이다. 다시 말해, 주어진 수들의 공배수 중에서 가장 작은 수를 의미한다. 최소공배수는 분수를 소수로 표현할 때 유용하다. 또한, 두 수의 공배수 중에서 가장 작은 수를 구할 때도 활용된다.

최대공약수와 최소공배수는 수학뿐만 아니라 다양한 분야에서 사용되며, 알고리즘 문제 등에도 자주 등장한다. 따라서 이 두 개념을 잘 이해하고 계산하는 방법을 알아두는 것이 중요하다. 앞으로는 최대공약수와 최소공배수를 구하는 방법에 대해 알아보도록 하겠다.

2. 최대공약수 구하는 방법

여러 가지 방법으로 최대공약수를 구할 수 있지만, 가장 대표적인 방법은 유클리드 호제법이다.

유클리드 호제법 (Euclidean Algorithm)

유클리드 호제법은 두 수의 최대공약수를 구하는 가장 일반적인 방법이다. 이 방법은 19세기 수학자인 유클리드에 의해 처음 소개되었으며, 지금도 널리 사용되고 있는 알고리즘이다.

유클리드 호제법의 원리는 다음과 같다. 주어진 두 수를 A, B라고 할 때, A를 B로 나눈 나머지를 R이라고 한다. 이때, A와 B의 최대공약수는 B와 R의 최대공약수와 같다. 이를 반복하여 나머지가 0이 될 때까지 계산을 반복하면, 최종적으로 나머지가 0이 되는 때의 나누는 수가 최대공약수이다.

유클리드 호제법은 재귀적으로 구현할 수도 있으며, 반복문을 사용하여 구현할 수도 있다. 둘 중에 어떤 방법을 선택해도 결과는 동일하다.

다음은 유클리드 호제법을 사용하여 최대공약수를 구하는 C++ 코드의 예이다.

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

위의 코드에서 gcd 함수는 두 수 a와 b의 최대공약수를 반환한다. 함수 내부에서는 b가 0이 될 때까지 a와 b를 반복적으로 나누어주는 과정을 진행하고, 최종적으로 a를 반환한다.

이와 같이 유클리드 호제법을 사용하면 효율적으로 최대공약수를 구할 수 있다.

3. 최소공배수 구하는 방법

최소공배수를 구하는 방법에는 여러 가지가 있지만, 가장 대표적인 방법은 최대공약수를 이용하는 방법이다.

최대공약수를 이용한 방법

두 수 A와 B의 최소공배수는 A와 B의 곱을 최대공약수로 나눈 값과 같다. 즉, LCM(A, B) = (A * B) / GCD(A, B)로 표현할 수 있다.

따라서, 최대공약수를 먼저 구하고 이를 이용하여 최소공배수를 계산할 수 있다. 앞에서 알아본 유클리드 호제법을 사용하여 최대공약수를 구한 후에, 위의 식을 이용하여 최소공배수를 계산할 수 있다.

다음은 C++ 코드의 예시이다.

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

int lcm(int a, int b) {
    int gcdValue = gcd(a, b);
    return (a * b) / gcdValue;
}

위의 코드에서 lcm 함수는 두 수 a와 b의 최소공배수를 반환한다. 함수 내부에서는 gcd 함수를 사용하여 최대공약수를 먼저 구한 후, 식 (A * B) / GCD(A, B)를 계산하여 최소공배수를 구한다.

이와 같이 최대공약수를 구한 후 이를 이용하여 최소공배수를 구하는 방법은 간단하면서도 효율적인 방법이다.