두 수의 최소공배수(LCM)를 구하는 알고리즘

최소공배수(LCM)란?

수학에서 최소공배수(Least Common Multiple, LCM)는 두 숫자 모두를 나누어떨어뜨릴 수 있는 가장 작은 양의 정수를 의미합니다.

최소공배수는 소인수분해 등 여러 가지 방법으로 구할 수 있습니다. 이 글에서 소개하는 알고리즘은 더 큰 수에 1, 2, 3… n을 차례대로 곱해 가면서, 그 결과가 두 번째 숫자로도 나누어떨어지는지 확인하는 방식을 사용합니다.

입력 및 출력

입력:
두 숫자: 6과 9
출력:
최소공배수: 18

알고리즘

LCMofTwo(a, b)

입력: 두 숫자 a와 b (단, a > b라고 가정)

출력: a와 b의 최소공배수

Begin
    lcm := a
    i := 2
    while lcm mod b ≠ 0, do
        lcm := a * i
        i := i + 1
    done

    return lcm
End

동작 원리

예를 들어 6과 9의 최소공배수를 구한다고 가정해 보겠습니다. 더 큰 수인 9를 기준으로 삼고, 9에 1부터 차례대로 곱한 값이 6으로 나누어떨어지는지 검사합니다.

• 9 × 1 = 9 → 9 ÷ 6은 나누어떨어지지 않음
• 9 × 2 = 18 → 18 ÷ 6 = 3, 나누어떨어짐 ✔

따라서 6과 9의 최소공배수는 18입니다.

C++ 구현 예제

#include<iostream>
using namespace std;

int findLCM(int a, int b) {    // a가 b보다 크다고 가정
    int lcm = a, i = 2;

    while(lcm % b != 0) {    // b의 배수가 되는 수를 찾음
        lcm = a*i;
        i++;
    }
    return lcm;    // a와 b의 최소공배수 반환
}

int lcmOfTwo(int a, int b) {
    int lcm;
    if(a>b)    // 첫 번째 인자가 항상 더 크도록 전달
        lcm = findLCM(a,b);
    else
        lcm = findLCM(b,a);
    return lcm;
}

int main() {
    int a, b;
    cout << "Enter Two numbers to find LCM: "; cin >> a >> b;
    cout << "The LCM is: " << lcmOfTwo(a,b);
}

실행 결과

Enter Two numbers to find LCM: 6 9
The LCM is: 18

이 알고리즘은 직관적이고 구현이 간단하지만, 두 수의 차이가 클 경우 반복 횟수가 늘어나 비효율적일 수 있습니다. 실무에서는 유클리드 호제법(GCD)을 이용해 LCM = (a × b) / GCD(a, b) 공식으로 구하는 것이 더 효율적인 선택이 될 수 있습니다.