C++로 두 수의 최소공배수(LCM)를 구하는 프로그램

최소공배수(LCM, Least Common Multiple)란 두 수의 공통 배수 중 가장 작은 수를 의미합니다.

예를 들어, 15와 9라는 두 수가 있다고 가정해 보겠습니다.

15 = 5 * 3
9 = 3 * 3

두 수의 공통 인수는 3이므로, 15와 9의 최소공배수는 45입니다.

방법 1: 반복문을 이용한 LCM 계산

두 수의 최소공배수를 구하는 첫 번째 방법은 반복문을 사용하는 것입니다. 아래 예제 코드를 살펴보겠습니다.

예제

#include <iostream>
using namespace std;
int main() {
    int a=7, b=5, lcm;
    if(a>b)
    lcm = a;
    else
    lcm = b;
    while(1) {
        if( lcm%a==0 && lcm%b==0 ) {
            cout<<"The LCM of "<<a<<" and "<<b<<" is "<<lcm;
            break;
        }
        lcm++;
    }
    return 0;
}

출력 결과

The LCM of 7 and 5 is 35

코드 설명

위 프로그램에서는 먼저 변수 lcm을 두 수 중 더 큰 값으로 초기화합니다. 최소공배수는 항상 두 수 중 큰 수 이상이기 때문에, 여기서부터 탐색을 시작하면 효율적입니다.

if(a>b)
lcm = a;
else
lcm = b;

이후 while 반복문이 실행됩니다. 반복문 안에서 현재 lcm 값이 a와 b 모두로 나누어 떨어지면, 그 값이 바로 두 수의 최소공배수이므로 화면에 출력하고 반복문을 종료합니다. 만약 조건을 만족하지 않으면 lcm 값을 1씩 증가시키며 조건이 충족될 때까지 반복합니다.

while(1) {
    if( lcm%a==0 && lcm%b==0 ) {
        cout<<"The LCM of "<<a<<" and "<<b<<" is "<<lcm;
        break;
    }
    lcm++;
}

방법 2: GCD(최대공약수) 공식을 이용한 LCM 계산

두 수의 최소공배수를 구하는 또 다른 방법은 LCM과 GCD의 관계를 이용하는 것입니다. 이 공식은 다음과 같습니다.

a * b = GCD * LCM

즉, 두 수의 곱은 그들의 최대공약수(GCD)와 최소공배수(LCM)의 곱과 같습니다. 따라서 LCM = (a × b) / GCD로 계산할 수 있습니다. 이 공식을 활용한 프로그램은 다음과 같습니다.

예제

#include<iostream>
using namespace std;
int gcd(int a, int b) {
    if (b == 0)
    return a;
    return gcd(b, a % b);
}
int main() {
    int a = 7, b = 5;
    cout<<"LCM of "<< a <<" and "<< b <<" is "<< (a*b)/gcd(a, b);
    return 0;
}

출력 결과

LCM of 7 and 5 is 35

코드 설명

위 프로그램에서는 공식을 이용해 최소공배수를 구합니다. 먼저 gcd() 함수를 호출하여 a와 b의 최대공약수를 구합니다. 이 함수는 재귀적으로 동작하며, 매개변수로 a와 b를 받습니다. b가 0이면 a를 main() 함수로 반환하고, 그렇지 않으면 자기 자신을 b와 a%b 값을 인수로 하여 재귀 호출합니다. 이것이 유클리드 호제법(Euclidean Algorithm)입니다.

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

최대공약수를 구한 후에는 앞서 소개한 공식인 (a × b) / GCD를 이용해 최소공배수를 계산하고, 그 결과를 화면에 출력합니다.

cout<<"LCM of "<< a <<" and "<< b <<" is "<< (a*b)/gcd(a, b);

마무리

반복문을 이용한 방법은 직관적이지만 숫자가 커지면 연산 횟수가 많아질 수 있습니다. 반면 GCD 공식을 활용한 방법은 유클리드 호제법 덕분에 더 빠르고 효율적으로 최소공배수를 구할 수 있으므로, 실제 개발에서는 두 번째 방법을 권장합니다.