[코풀수: 산술] 소인수 분해

날짜:

소인수 분해란?


어떤 자연수를 소인수 분해한다는 것은 소수(Prime Number)의 곱으로 나타낸다는 것이다. 소수에 대해 더 알고 싶으면 소수의 개수 에 대한 글을 참고하기 바란다.

수(Number)에 대해서 더 알고 싶으면 허수에 대하여 를 참고하기 바란다.


가령 12를 소인수 분해한다고 하면 다음과 같다.


소인수 분해

N:



답:

소인수 분해 알고리즘


어떤 수 N에 대한 소인수 분해는 다음과 같이 생각할 수 있다.

  1. N을 2부터 N의 제곱근까지 1씩 증가시켜 가면서 나누어 나머지가 0인지 체크한다.
  2. 나머지가 0인수가 나오면 그 나눈 수를 인수로 저장하고 그 몫에 대해 똑같이 반복한다.

어떤 수의 인수는 2보다 크거나 같고 그 수의 제곱근보다 작거나 같기 때문에 제곱근보다 큰 값으로 나눠볼 필요가 없다.

<!DOCTYPE html>
<html>
<title>소인수 분해</title>
<body>

<h4>소인수 분해(Prime Factorization)</h4>

<form>
  N: <input type="text" id="N" value="12"><br>
  <input type="button" id="factorization" value="소인수분해"><br>
</form>

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

<script>
    document.getElementById("factorization").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 str = N + " = ";
        for (var k = 0; k < primeArray.length; k++) {
            str += primeArray[k];
            if (k < primeArray.length - 1) str += "x";
        }

        document.getElementById("result").innerHTML = "답: " + str;
    }

    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>

입력 폼은 단순하다. 수를 입력하고 소인수분해를 실행할 버튼만 있다. 스크립트는 매우 복잡해 졌다.

  1. 먼저 입력한 값이 자연수인지를 체크하고,
  2. primeFactors()라는 함수를 통해 소인수들은 구하고
  3. 이것을 소인수 분해를 표현하는 문자열로 만든다.

[코드설명] for (var k = 0; k < 10; k++) {}는 k를 0부터 10 전까지 1씩 증가시켜 어떤 일을 반복하라는 것이다.

[코드설명] while (n > 2) {}는 n이라는 변수가 2보다 클 동안(while)은 계속해서 괄호안의 내용을 반복하라는 것이다.

[코드설명] var factors = [] 는 어레이(Array)로 인수로 구해진 값들이 한 개가 아니어서 그 값들을 차례로 저장하기 위한 것이다. 이것을 길이(값들의 개수)는 factors.length이고, 값을 추가할 때는 factors.push()라는 함수를 이용하면 된다.

댓글

댓글 쓰기