[코풀수: 산술] 최소 공배수 (최대 공약수 이용)

날짜:
앞의 글에서 소인수 분해 를 이용하여 최소 공배수 를 구하는 알고리즘에 대해 소개하였다. 입력한 두 수를 소인수 분해해서 모든 소인수와 그에 해당하는 최대 지수를 구해야 해서 알고리즘 상으로는 구현이 복잡했다. 유클리드 호제법으로 최대 공약수 를 구하는 매우 간단한 알고리즘을 배웠기 때문에, 최소 공배수와 최대 공약수의 관계를 통해 쉽게 최소 공배수를 구하는 알고리즘을 알아보자.


최소 공배수와 최대 공약수의 관계


두 자연수 N과 M의 최대 공약수가 G이고 최소 공배수가 L이라고 하면, 아래 수식을 유도할 수 있다.


n과 m이 서로소이고, 서로소인 것의 최소 공배수는 두 수의 곱이다. 결론적으로 말하면, 두 수의 곱을 최대 공약수와 최소 공배수의 곱과 같다.


최소 공배수 (최대 공약수 이용)

N:

M:



답:

코딩은 매우 간단하다. 두 수를 곱하고, 최대 공약수를 나누면 된다. 수식과 코딩은 단순한 것이 가장 좋다. Simple is the Best.

<!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;
        }

        // GCD 및 LCM 계산
        var gcd = getGCD(N, M);
        var lcm = N * M / gcd;
        document.getElementById("result").innerHTML = N + "과 " + M + "의 최소공배수는 " + lcm + "입니다.";
    }

    function getGCD(n, m) {
        return n%m ? getGCD(m, n%m) : m;
    }
</script>

</body>
</html>

댓글

댓글 쓰기