최소공배수 (LCM)

 최소공배수(The Least Common Multiple)는  두 개 또는  그 이상의 자연수에서 공통으로 나오는 배수 중 가장 작은 값을 의미합니다. 이를 계산하는 방법은 다음과 같습니다.

 

1. 공약수로 나누기: 입력한 자연수가 서로소가 될 때까지 공약수로 계속 나누는 방법

     예) LCM(24, 20) = 120

      →  2  )_ 24 , 20 

      →  2  )_12 , 10 

                    6 ,   5 

      → 최소공배수(LCM)= 2*2*6*5 = 120, 참고로 최대공약수(GCD) =  2*2 = 4.

 

2. 소인수 분해: 각 수를 소인수 분해하여 소인수 중 최대 지수를 선택해 곱하는 방법

    예) LCM(24, 20) = 120

    →  24 = 2³ * 3¹  , 20 = 2² * 5¹  ,

    →  두  수의 최대지수 선택: 2³ * 3¹ * 5¹ = 120.

 

3. 유클리드 알고리즘을 활용한 방법: 최대공약수를 구한후, 두 수의 곱을 GCD로 나누어 최소공배수를 계산

    예) LCM(24, 20) = 120

    →  LCM = 24 x 20 / GCD(24, 18) = 24 x 20 / 4 = 120.   

최소공배수 계산방법

 

이번 게시글은 암호와는 별개로 앞에서 설명한 유클리드 알고리즘을 활용하는 방법으로 최소공배수를 구하는 방법이 있다는 것으로 마무리하겠습니다.