[코풀수: 산술] 최소 공배수

날짜:
자연수에서 중요한 소인수 분해 , 약수 구하기 , 최대 공약수 를 배웠다. 이제 최소 공배수를 배워보자.


최소 공배수란?


두 개의 수가 주어졌을 때, 공통의 배수 중 가장 작은 것을 최소 공배수(Least Common Multiple, LCM)라고 한다. 최소 공배수는 분수끼리 더할 때 사용되는 통분에 이용된다.

예를 들어 24와 15의 최소 공배수를 구해보자.
24 = 2x2x2x3이고,
15 = 3x5이다.
따라서 LCM = 2x2x2x3x5 = 120이다.

최소 공배수

N:

M:



답:

위와 같이 소인수 분해를 이용하면 최소 공배수를 쉽게 구할 수 있다.

소인수 분해 이용하기


기본적인 알고리즘은 다음과 같다.

  1. 입력된 N과 M을 소인수 분해하고, 소인수와 그 지수(계승)을 구한다.
  2. 구해진 소인수와 그에 해당하는 최대 지수를 구한다.
  3. 최소 공배수를 구한다.

<!DOCTYPE html>
<html>
<title>최소 공배수</title>
<body>

<h4>최소 공배수</h4>

<form>
  N: <input type="text" id="N" value="24"><br><br>
  M: <input type="text" id="M" value="15"><br><br>
  <input type="button" id="find_lcm" value="최소공배수 구하기"><br><br>
</form>

<p id="result">답: </p>

<script>
    document.getElementById("find_lcm").addEventListener("click", calc);
    
    function calc() {
        // 입력된 문자열을 숫자로 바꾸고, 자연수인지를 체크하기
        N = Number(document.getElementById("N").value);
        if (isNaN(N) || N < 1 || N % 1 != 0) {
            document.getElementById("result").innerHTML = "자연수를 입력하세요.";
            return;
        }
        M = Number(document.getElementById("M").value);
        if (isNaN(M) || M < 1 || M % 1 != 0) {
            document.getElementById("result").innerHTML = "자연수를 입력하세요.";
            return;
        }

        // 소인수 분해하기하고 소인수와 계승 찾기
        var primeArrayOfN = primeFactors(N);
        var divisors_pOfN = [];
        var divisors_kOfN = [];
        findPrimesAndPowers(primeArrayOfN, divisors_pOfN, divisors_kOfN);
        var primeArrayOfM = primeFactors(M);
        var divisors_pOfM = [];
        var divisors_kOfM = [];
        findPrimesAndPowers(primeArrayOfM, divisors_pOfM, divisors_kOfM);

        // 소인수 찾기 (적어도 하나라도 있는 것)
        var divisors_pCommon = [];
        for (var i = 0; i < divisors_pOfN.length; i++) {
            if (divisors_pCommon.includes(divisors_pOfN[i]) == false) {
                divisors_pCommon.push(divisors_pOfN[i]);
            }
        }
        for (var i = 0; i < divisors_pOfM.length; i++) {
            if (divisors_pCommon.includes(divisors_pOfM[i]) == false) {
                divisors_pCommon.push(divisors_pOfM[i]);
            }
        }
        
        // 최대 지수(계승) 찾기
        var divisors_kCommon = [];
        for (var j = 0; j < divisors_pCommon.length; j++) {
            divisors_kCommon.push(1);
            for (var i = 0; i < divisors_pOfN.length; i++) {
                if (divisors_pCommon[j] == divisors_pOfN[i]) {
                    if (divisors_kCommon[j] < divisors_kOfN[i]) {
                        divisors_kCommon[j] = divisors_kOfN[i]
                    }
                    break;
                }
            }
            for (var i = 0; i < divisors_pOfM.length; i++) {
                if (divisors_pCommon[j] == divisors_pOfM[i]) {
                    if (divisors_kCommon[j] < divisors_kOfM[i]) {
                        divisors_kCommon[j] = divisors_kOfM[i]
                    }
                    break;
                }
            }
        }

        // 최대공약수 계산하기
        var lcm = 1;
        for (var j = 0; j < divisors_pCommon.length; j++) {
            lcm *= Math.pow(divisors_pCommon[j], divisors_kCommon[j]);
        }
        document.getElementById("result").innerHTML = N + "과 " + M + "의 최소공배수는 " + lcm + "입니다.";
    }

    function primeFactors(n) {
        var factors = []; 
        var divisor = 2;

        while (n > 2) {
            if(n % divisor == 0) {
                factors.push(divisor); 
                n = n / divisor;
            }
            else {
                divisor++;
            }     
        }
        return factors;
    }

    function findPrimesAndPowers(primeArray, divisors_p, divisors_k) {
        for (var i = 0; i < primeArray.length; i++) {
            if (divisors_p.includes(primeArray[i]) == false) {
                divisors_p.push(primeArray[i]);
            }
        }

        for (var j = 0; j < divisors_p.length; j++) {
            divisors_k.push(0);
            for (var i = 0; i < primeArray.length; i++) {
                if (divisors_p[j] == primeArray[i]) {
                    divisors_k[j] += 1;
                }
            }
        }
    }
</script>

</body>
</html>

소스 코드가 상당히 길고 복잡하다. 최대 공약수와 최소 공배수의 관계를 이용한 아주 간단한 방법이 있다.

댓글

댓글 쓰기