C#으로 최대공약수(GCD)와 최소공배수(LCM) 구하는 프로그램 작성 방법

최대공약수(GCD)란?

GCD(Greatest Common Divisor, 최대공약수)는 두 개 이상의 정수를 모두 나눌 수 있는 가장 큰 양의 정수를 의미합니다. 예를 들어 10과 16의 최대공약수는 2입니다.

최소공배수(LCM)란?

LCM(Least Common Multiple, 최소공배수)은 두 수 모두로 나누어 떨어지는 가장 작은 정수를 뜻합니다. 10과 16의 경우 최소공배수는 80이 됩니다.

다음 예제에서는 유클리드 호제법(Euclidean Algorithm)을 사용하여 10과 16의 GCD를 먼저 구한 뒤, 이를 활용해 LCM을 계산합니다. LCM은 두 수의 곱을 GCD로 나누면 손쉽게 구할 수 있습니다.

예제 코드

using System;

namespace Demo {
    class Program {
        static void Main(string[] args) {

            int val1, val2, n1, n2, x;
            int resLCM, resGCD;
            val1 = 10;
            val2 = 16;

            n1 = val1;
            n2 = val2;

            // 유클리드 호제법으로 GCD 계산
            while (n2 != 0) {
                x = n2;
                n2 = n1 % n2;
                n1 = x;
            }

            resGCD = n1;
            resLCM = (val1 * val2) / resGCD;

            Console.WriteLine("{0}과 {1}의 LCM: {2}", val1, val2, resLCM);
            Console.WriteLine("{0}과 {1}의 GCD: {2}", val1, val2, resGCD);
            Console.ReadKey();
        }
    }
}

실행 결과

10과 16의 LCM: 80
10과 16의 GCD: 2

코드 설명

유클리드 호제법은 두 수 중 큰 수를 작은 수로 나눈 나머지를 반복적으로 계산하다가, 나머지가 0이 되는 순간의 몫이 곧 최대공약수가 되는 원리를 이용합니다. while 루프 안에서 n1 % n2 연산을 통해 나머지를 구하고, 두 변수의 값을 교환하며 계산을 진행합니다.

이후 (val1 * val2) / resGCD 공식을 적용하면 최소공배수를 구할 수 있습니다. 참고로 오버플로우를 방지하려면 ((long)val1 * val2) / resGCD처럼 형 변환을 활용하는 것이 안전합니다.