최소 공배수(Least Common Multiple)

최소 공배수란?

2개 이상의 수의 공배수 중 가장 작은 수

5의 배수 : 5, 10, 15, 20. 25, 30. 35, 40...

7의 배수 : 7, 14, 21, 27, 35, 42...

5와 7의 최소 공배수 = 35

식으로 나타내면

f(X, Y)는 정수 X와 Y의 최소 공배수

G는 정수 X와 Y의 최대 공약수

라고 할때

f(X, Y) = (X × Y) / G

이다

물론, 이러한 수학식을 몰라도

최소 공배수를 구할 수 있다.

int Algorithm::LeastCommonMultiple(int num01, int num02)

{

//더 큰 수를 시작 점으로

        int num = num01 > num02 ? num01 : num02;

 

//최소 공배수를 찾을 때까지 반복

        while(true)

        {

//제일 먼저 두 수 모두로 나눠떨어지는 수가 최소 공배수

               if ((num % num01 == 0) && (num % num02 == 0))

               {

                       return num;

               }

               //찾을때까지 1씩 더함

               num++;

        }

}

하지만 최대 공약수와 위의 식을 활용하면

조금 더 효율적으로 최소 공배수를 구할 수 있다.

최대 공약수는 유클리드 호제법을 활용하면 쉽게 구할 수 있다.

최대 공약수 & 유클리드 호제법 보기(클릭)

int Algorithm::LeastCommonMultiple(int num01, int num02)

{

        int Divisor;                    //최대 공약수

        int Multiple = num01 * num02;   //두 수의 곱

       

        //최대 공약수 구함

        while (num02)

        {

               Divisor = num01 % num02;

               num01 = num02;

               num02 = Divisor;

        }

 

        Divisor = num01;

 

        return Multiple / Divisor;

}