[코풀수: 산술] 최대 공약수

날짜:

최대 공약수란?


두 개의 수가 주어졌을 때, 공통의 약수 중 가장 큰 것을 최대 공약수(Greatest Common Divisor, GCD)라고 한다. 최대 공약수가 1인 수들은 서로소(Coprime)라고 한다. 공약수는 최대 공약수의 약수이다.


간단한 예를 들어보자.
12의 약수는 1, 2, 3, 4, 6, 12이고,
18의 약수는 1, 2, 3, 6, 9, 18이다.
따라서 이 두 수의 최대 공약수는 6이다. 그리고 공약수는 6의 약수인 1, 2, 3, 6로 총 4개이다.

최대 공약수

N:

M:



답:

최대 공약수를 구하는 방법은 크게 2가지가 있다. 유클리드 호제법(互除法)과 소인수 분해 를 이용하는 것이다.

소인수 분해 이용하기


위에서 예를 들었던 12와 18를 각각 소인수 분해 해보자.



공통인 것만 찾으려면 공통의 소인수를 찾고 그것의 지수 중 낮은 것을 고르면 된다.


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

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

<!DOCTYPE html>
<html>
<title>최대 공약수</title>
<body>

<h4>최대 공약수</h4>

<form>
  N: <input type="text" id="N" value="12"><br>
  M: <input type="text" id="M" value="18"><br>
  <input type="button" id="find_gcd" value="최대공약수 구하기"><br>
</form>

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

<script>
    document.getElementById("find_gcd").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_pOfM.includes(divisors_pOfN[i]) == true) {
                divisors_pCommon.push(divisors_pOfN[i]);
            }
        }
        
        // 공통의 최소 계승 찾기
        var divisors_kCommon = [];
        for (var j = 0; j < divisors_pCommon.length; j++) {
            for (var i = 0; i < divisors_pOfN.length; i++) {
                if (divisors_pCommon[j] == divisors_pOfN[i]) {
                    divisors_kCommon.push(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;
                }
            }
        }

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

    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>

소스 코드가 상당히 길고 복잡하다. 유클리드 호제법을 이용한 아주 간단한 방법이 있다.

댓글

댓글 쓰기