[코풀수: 산술] 약수 구하기

날짜:

약수란?


소인수 분해 를 통해 자연수의 소인수를 구할 수 있게 되었다. 이제 이것을 이용하여 약수 및 약수의 개수를 구해보자.


먼저 약수가 뭔지 간단히 알아보자. N의 약수는 나누어 떨어지는(나머지가 0인) N보다 같거나 작은 자연수들이다. 예를 들어 72의 약수는 1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72로 12개나 된다.

약수 구하기 #1


약수 구하기

N:



답:

먼저 가장 쉬운 알고리즘은 다음과 같다.

  1. N을 2부터 N/2까지 1씩 증가시켜 가면서 나누어 나머지가 0인지 체크한다.
  2. 이 나눈 수가 약수이다, 그리고 1과 N도 약수가 된다.

<!DOCTYPE html>
<html>
<title>약수 구하기</title>
<body>

<h4>약수 구하기</h4>

<form>
  N: <input type="text" id="N" value="72"><br>
  <input type="button" id="find_divisors" value="약수 구하기"><br>
</form>

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

<script>
    document.getElementById("find_divisors").addEventListener("click", calc);
    
    function calc() {
        N = Number(document.getElementById("N").value);
        if (isNaN(N) || N < 1 || N % 1 != 0) {
            document.getElementById("result").innerHTML = "자연수를 입력하세요.";
            return;
        }

        var divisors = [];
        divisors.push(1);
        for (var i = 2; i <= N/2; i++) {
            if(N % i == 0) {
                divisors.push(i);
            } 
        }
        if (N > 1) divisors.push(N);

        var str = N + ": ";
        for (var k = 0; k < divisors.length; k++) {
            str += divisors[k];
            if (k < divisors.length - 1) str += ", ";
        }

        document.getElementById("result").innerHTML = str + " (총: " + divisors.length + "개)";
    }
</script>

</body>
</html>

폼은 간단하고, 스크립트에는 크게 약수를 구하는 부분과 그것을 문자열로 만들어서 출력하는 부분으로 나뉘어 있다.

약수 구하기 #2


이제 소인수 분해를 이용하는 방법을 알아보자. 먼저 N을 소인수 분해하면 아래와 같이 나타난다고 하자.


새로운 기호가 나와서 복잡해 보이는데, 72를 예로 들어 위의 수식과 같이 나타내보자.


약수의 개수는 다음과 같다.


그리고 각 약수들은 다음과 같다.


여기서


복잡해 보이는데, 약수는 아래의 곱하기의 전개한 결과의 각 인자값과 같다.


<!DOCTYPE html>
<html>
<title>약수 구하기 #2</title>
<body>

<h4>약수 구하기 #2</h4>

<form>
  N: <input type="text" id="N" value="72"><br>
  <input type="button" id="find_divisors" value="약수 개수 구하기"><br>
</form>

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

<script>
    document.getElementById("find_divisors").addEventListener("click", calc);
    
    function calc() {
        N = Number(document.getElementById("N").value);
        if (isNaN(N) || N < 1 || N % 1 != 0) {
            document.getElementById("result").innerHTML = "자연수를 입력하세요.";
            return;
        }

        var primeArray = primeFactors(N);

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

        var divisors_k = [];
        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;
                }
            }
        }

        var num_divisors = 1;
        for (var i = 0; i < divisors_k.length; i++) {
            num_divisors *= (divisors_k[i] + 1);
        }

        document.getElementById("result").innerHTML = N + "의 약수는 " + num_divisors + "개 입니다.";
    }

    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;
    }
</script>

</body>
</html>

첫번째 알고리즘보다 복잡해 보이긴 하는데, 큰 수에 대해서 약수를 구할 때는 더 빠르다.

약수 구하기 #2

N:



답:

댓글

댓글 쓰기