C++로 두 수의 최대공약수(GCD)와 최소공배수(LCM) 구하는 방법

이 글에서는 C++를 이용해 숫자들의 최대공약수(GCD)와 최소공배수(LCM)를 구하는 방법을 알아봅니다.

최대공약수(Greatest Common Divisor, GCD)란 0이 아닌 두 개 이상의 정수를 모두 나누어 떨어지게 하는 가장 큰 양의 정수를 의미합니다. 흔히 '최대 공통 인수(Greatest Common Factor)'라고도 부릅니다.

최소공배수(Least Common Multiple, LCM)는 두 수의 공통 배수 중에서 0이 아닌 가장 작은 수를 말합니다.

알고리즘

시작
    두 개의 숫자를 입력받는다
    gcd() 함수를 호출하여 최대공약수를 구한다
    lcm() 함수를 호출하여 최소공배수를 구한다

gcd(number1, number2)
    변수 r, a, b 선언
    r = 0
    a = (number1 > number2) ? number1 : number2
    b = (number1 < number2) ? number1 : number2
    r = b
    while (a mod b != 0)
        반복
            r = a mod b
            a = b
            b = r
        return r
    종료

lcm(number1, number2)
    변수 a 선언
    a = (number1 > number2) ? number1 : number2
    while(true)
        만약 (a mod number1 == 0 그리고 a mod number2 == 0)
            return a
        a를 1씩 증가
종료

예제 코드

#include<iostream>
using namespace std;
int gcd(int m, int n) {
    int r = 0, a, b;
    a = (m > n) ? m : n;
    b = (m < n) ? m : n;
    r = b;
    while (a % b != 0) {
        r = a % b;
        a = b;
        b = r;
    }
    return r;
}
int lcm(int m, int n) {
    int a;
    a = (m > n) ? m : n;
    while (true) {
        if (a % m == 0 && a % n == 0)
            return a;
        ++a;
    }
}
int main(int argc, char **argv) {
    cout << "Enter the two numbers: ";
    int m, n;
    cin >> m >> n;
    cout << "The GCD of two numbers is: " << gcd(m, n) << endl;
    cout << "The LCM of two numbers is: " << lcm(m, n) << endl;
    return 0;
}

코드 설명

gcd() 함수 — 유클리드 호제법

gcd() 함수는 고전적인 유클리드 호제법(Euclidean Algorithm)을 사용합니다. 먼저 두 수 중 큰 값을 a, 작은 값을 b에 저장한 뒤, a를 b로 나눈 나머지를 구하고, 이후에는 a에 b를, b에 나머지를 대입하는 과정을 나머지가 0이 될 때까지 반복합니다. 반복이 끝난 시점의 r 값이 바로 최대공약수입니다.

lcm() 함수 — 공통 배수 탐색

lcm() 함수는 두 수 중 더 큰 값부터 시작하여 1씩 증가시키면서, 해당 값이 두 수 모두로 나누어 떨어지는 첫 번째 지점을 찾습니다. 이 값이 곧 최소공배수입니다.

n개의 수로 확장하기

세 개 이상의 숫자에 적용하려면 다음 성질을 활용하면 됩니다.

GCD(a, b, c) = GCD(GCD(a, b), c)
LCM(a, b, c) = LCM(LCM(a, b), c)

즉, 앞에서 구한 결과와 다음 숫자를 차례대로 함수에 전달하면 임의의 n개 숫자에 대해서도 확장할 수 있습니다.

실행 결과

Enter the two numbers:
7
6
The GCD of two numbers is: 1
The LCM of two numbers is: 42

위 실행 예시에서 입력한 7과 6은 서로소이므로 최대공약수는 1이 되며, 최소공배수는 두 수를 곱한 42가 됩니다.