JavaScript로 숫자의 모든 소인수 구하기

이번 글에서는 숫자 하나를 입력받아 해당 숫자를 나눌 수 있는 모든 소수, 즉 소인수를 배열 형태로 반환하는 JavaScript 함수를 작성해 보겠습니다.

문제 이해하기

소인수란 어떤 수를 나머지 없이 정확히 나누면서 동시에 소수인 숫자를 의미합니다. 예를 들어 입력값이 18이라면, 18을 완전히 나눌 수 있는 소수는 2와 3뿐입니다.

따라서 기대되는 결과는 다음과 같습니다.

const output = [2, 3];

구현 방법

이 문제는 두 단계로 나누어 해결할 수 있습니다.

1단계 - 소수 판별 함수 작성: 먼저 특정 숫자가 소수인지 확인하는 isPrime 함수가 필요합니다. 2부터 n/2까지의 수로 차례대로 나누어 보고, 하나라도 나누어 떨어지면 소수가 아닙니다.

2단계 - 약수 탐색: 다음으로 2부터 시작해 입력 숫자까지 반복하면서, 나누어 떨어지는 약수 중 소수인 값만 결과 배열에 담습니다.

코드 예시

const num = 18;

// 소수 여부를 판별하는 함수
const isPrime = (n) => {
    for(let i = 2; i <= n/2; i++){
        if(n % i === 0){
            return false;
        }
    };
    return true;
};

// 소인수를 찾는 메인 함수
const findPrimeFactors = num => {
    const res = num % 2 === 0 ? [2] : [];
    let start = 3;
    while(start <= num){
        if(num % start === 0){
            if(isPrime(start)){
                res.push(start);
            };
        };
        start++;
    };
    return res;
};

console.log(findPrimeFactors(18));

실행 결과

위 코드를 실행하면 콘솔에 다음과 같은 결과가 출력됩니다.

[2, 3]

동작 원리 살펴보기

코드가 실행되는 과정을 단계별로 살펴보면 다음과 같습니다.

먼저 입력된 숫자가 2로 나누어 떨어지는지 확인합니다. 만약 그렇다면 결과 배열에 2를 미리 넣어둡니다. 18은 2로 나누어 떨어지므로 배열은 [2]에서 시작합니다.

그다음 3부터 숫자 자기 자신까지 반복하면서 각 값으로 나누어 떨어지는지 검사하고, 나누어 떨어지는 경우 isPrime 함수로 해당 값이 소수인지 추가로 확인합니다. 18의 경우 3이 약수이자 소수이므로 최종적으로 [2, 3]이 반환됩니다.

이처럼 소수 판별과 약수 탐색 로직을 조합하면, 어떤 숫자든 손쉽게 소인수 목록을 구할 수 있습니다.