JavaScript로 숫자를 소수의 거듭제곱 곱 형태로 표현하는 방법

문제 정의

양의 정수 하나를 입력받아, 해당 숫자를 소수들의 거듭제곱 곱으로 분해한 결과를 지정된 형식의 문자열로 반환하는 JavaScript 함수를 작성하는 것이 목표입니다.

숫자 n이 주어졌을 때 함수는 아래와 같은 형태의 문자열을 반환해야 합니다.

n = "(p1**n1)(p2**n2)...(pk**nk)"

여기서 p1, p2, ..., pk는 소수이고, n1, n2, ..., nk는 각 소수의 지수(거듭제곱 횟수)입니다. ** 기호는 거듭제곱을 나타냅니다.

접근 방법: 소인수분해

이 문제의 핵심은 소인수분해(prime factorization)입니다. 산술의 기본정리에 따르면 모든 자연수는 유일하게 소수들의 곱으로 표현할 수 있으므로, 작은 소수부터 차례대로 나누어 지수를 세면 됩니다.

2부터 시작해 n을 나눌 수 있는 가장 작은 수를 찾습니다. 이 값은 반드시 소수입니다.
더 이상 나누어 떨어지지 않을 때까지 계속 나누며 지수를 카운트합니다.
지수가 2 이상이면 (p**n), 지수가 1이면 (p) 형태로 결과 문자열에 추가합니다.
n이 1이 될 때까지 위 과정을 반복합니다.

구현 코드

const primeFactors = (n) => {
  let str = '';
  for (let p = 2; p <= n; p++) {
    // p가 n의 약수라면 p는 반드시 소수
    if (n % p === 0) {
      let exponent = 0;
      while (n % p === 0) {
        n /= p;
        exponent++;
      }
      str += exponent > 1 ? `(${p}**${exponent})` : `(${p})`;
    }
  }
  return str;
};

console.log(primeFactors(86240));

실행 결과

(2**5)(5)(7**2)(11)

코드 설명

입력값 86240은 다음과 같이 분해됩니다.

86240 = 2 × 2 × 2 × 2 × 2 × 5 × 7 × 7 × 11 = 2⁵ × 5 × 7² × 11

따라서 최종 출력은 (2**5)(5)(7**2)(11)이 됩니다.

외부 for문: 2부터 시작해 후보 수 p를 하나씩 증가시킵니다. 더 작은 약수들이 먼저 제거되기 때문에, p가 n의 약수일 경우 p는 항상 소수입니다.
내부 while문: 현재 소수 p로 나누어 떨어지는 동안 계속 나누고, 몇 번 나눴는지 지수를 기록합니다.
문자열 조립: 지수가 1보다 크면 (p**지수) 형식으로, 정확히 1이면 (p)만 추가합니다.

성능 개선 팁

위 코드의 시간 복잡도는 대략 O(n)이지만, 반복 조건을 p * p <= n으로 바꾸면 O(√n)까지 최적화할 수 있습니다. 루프가 끝난 뒤 n이 1보다 크다면 남은 n 자체가 소수이므로 마지막에 추가해 주면 됩니다.

const primeFactorsFast = (num) => {
  let str = '';
  let n = num;
  for (let p = 2; p * p <= n; p++) {
    if (n % p === 0) {
      let e = 0;
      while (n % p === 0) { n /= p; e++; }
      str += e > 1 ? `(${p}**${e})` : `(${p})`;
    }
  }
  if (n > 1) str += `(${n})`;
  return str;
};