자바스크립트로 반소수(Semiprime) 판별하기

이번 글에서는 숫자를 입력받아 해당 숫자가 반소수(semiprime)인지 아닌지를 판별하는 자바스크립트 함수를 작성해 보겠습니다.

반소수(Semiprime)란?

반소수는 두 개의 소수의 곱으로 이루어진 특수한 형태의 합성수입니다. 예를 들어 6(=2×3), 15(=3×5), 10(=2×5), 77(=7×11)은 모두 반소수입니다. 또한 소수의 제곱 역시 반소수에 해당하며, 4(=2²), 9(=3²), 25(=5²) 등이 그 예입니다.

예제 코드

다음은 주어진 숫자가 반소수인지 확인하는 코드입니다 −

const num = 141;
const checkSemiprime = num => {
    let cnt = 0;
    for (let i = 2; cnt < 2 && i * i <= num; ++i){
        while (num % i == 0){
            num /= i, ++cnt;
        }
    }
    if (num > 1){
        ++cnt;
    }
    // 소인수의 개수가 정확히 2개면 true, 아니면 false 반환
    return cnt === 2;
}
console.log(checkSemiprime(num));

코드 동작 원리

이 알고리즘은 소인수 분해를 활용하여 다음과 같은 순서로 작동합니다.

• 2부터 시작해 √num까지의 수로 나누며 소인수 분해를 진행합니다.
• 나누어떨어질 때마다 소인수 개수를 세는 변수(cnt)를 1씩 증가시킵니다.
• 루프가 끝난 후 남은 값이 1보다 크다면 그 값 자체가 소수이므로 cnt를 하나 더 증가시킵니다.
• 최종적으로 소인수의 총 개수가 정확히 2개라면 true(반소수), 그렇지 않으면 false를 반환합니다.

예제의 141은 3 × 47로 분해되므로 두 소수의 곱에 해당하며, 결과적으로 true가 출력됩니다.

출력 결과

콘솔에 출력되는 결과는 다음과 같습니다 −

true