자바스크립트(JavaScript)에서 숫자의 가장 큰 소인수 찾는 방법

자바스크립트(JavaScript)에서 숫자 하나를 인수로 받아, 그 숫자를 나머지 없이 정확히 나누는 가장 큰 소수(소인수)를 찾는 함수를 작성해 보겠습니다.

문제 정의

함수에 전달되는 숫자는 반드시 합성수(composite number), 즉 두 개보다 많은 약수를 가진 수라고 가정합니다. 우리가 만들 함수는 이 입력값을 완전히 나누는 소수(prime number) 중에서 가장 큰 값을 반환해야 합니다.

예시 −

인수가 72라면 출력 결과는 3이어야 합니다.

그 이유는 72 = 2³ × 3² 이므로 72를 나눌 수 있는 소수는 2와 3뿐이고, 이 중 가장 큰 값이 3이기 때문입니다.

접근 방식: 소인수분해

가장 효율적이고 널리 쓰이는 방법은 시행 나눗셈(trial division) 기반의 소인수분해입니다. 로직은 다음과 같습니다.

가장 작은 소수인 2부터 시작해, 나누어 떨어지는 동안 계속 나누면서 해당 소인수를 기록합니다.
이후 3, 5, 7처럼 홀수만 검사하며 √num 범위까지만 확인합니다.
모든 나눗셈이 끝난 후 남은 값이 1보다 크다면, 그 값 자체가 가장 큰 소인수입니다.

예제 코드

다음은 위 로직을 구현한 전체 코드입니다 −

const num = 72;

const largestPrimeFactor = (num) => {
  let largest = 1;

  // 1) 2로 나누어 떨어지는 만큼 처리
  while (num % 2 === 0) {
    largest = 2;
    num /= 2;
  }

  // 2) 3부터 홀수만 √num까지 검사
  for (let i = 3; i * i <= num; i += 2) {
    while (num % i === 0) {
      largest = i;
      num /= i;
    }
  }

  // 3) 남은 값이 1보다 크면 그것이 가장 큰 소인수
  if (num > 1) {
    largest = num;
  }

  return largest;
};

console.log(largestPrimeFactor(num)); // 3
console.log(largestPrimeFactor(13195)); // 29
console.log(largestPrimeFactor(600851475143)); // 6857

출력 결과

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

3
29
6857

동작 원리 상세 설명

입력값이 72일 때 코드가 어떻게 진행되는지 단계별로 살펴보겠습니다.

2 처리 단계: 72는 2로 나누어 떨어지므로 largest = 2로 갱신하고, 72 → 36 → 18 → 9로 줄어듭니다.
홀수 검사 단계: i = 3일 때 9는 3으로 나누어 떨어지므로 largest = 3으로 갱신되고, 9 → 3 → 1이 됩니다.
루프 종료: num이 1이 되면 i * i <= num 조건을 더 이상 만족하지 않아 반복이 종료됩니다.
결과 반환: 마지막으로 기록된 largest 값인 3을 반환합니다.

시간 복잡도

이 알고리즘은 √num까지만 검사하면 되기 때문에 시간 복잡도는 O(√n)입니다. 따라서 매우 큰 숫자도 효율적으로 처리할 수 있으며, 실무에서도 가장 널리 사용되는 방식입니다.