JavaScript로 구현하는 소수 판별 (Prime Check)

소수란 무엇인가?

소수(Prime Number)는 1과 자기 자신만을 약수로 가지는 1보다 큰 자연수를 의미합니다. 예를 들어 2, 3, 5, 7, 11 등은 모두 소수이며, 4, 6, 8, 9 같은 수는 소수가 아닙니다. 소수는 암호학, 해시 함수, 수론 기반 알고리즘 등에 널리 활용되기 때문에 알고리즘 문제에서도 자주 등장합니다.

---

방법 1: 2부터 n-1까지 나누어 보기

가장 기본적인 소수 판별 방법은 주어진 수를 2부터 n-1까지 순차적으로 나누어 나누어떨어지는 수가 있는지 확인하는 것입니다.

function isPrimeBasic(n) {
  if (n < 2) return false;
  for (let i = 2; i < n; i++) {
    if (n % i === 0) return false;
  }
  return true;
}

console.log(isPrimeBasic(7));  // true
console.log(isPrimeBasic(10)); // false

장점: 개념적으로 단순하고 구현이 쉬움
단점: 수가 커질수록 반복 횟수가 많아져 비효율적

---

방법 2: 제곱근(√n)까지만 검사하기

모든 합성수는 √n 이하의 인수를 반드시 가지므로, √n까지만 검사해도 소수를 판별할 수 있습니다.

function isPrimeSqrt(n) {
  if (n < 2) return false;
  const limit = Math.floor(Math.sqrt(n));
  for (let i = 2; i <= limit; i++) {
    if (n % i === 0) return false;
  }
  return true;
}

console.log(isPrimeSqrt(29));  // true
console.log(isPrimeSqrt(100)); // false

장점: 반복 횟수를 대폭 줄일 수 있어 성능 향상
단점: 여전히 한 수씩 순차적으로 확인함

---

방법 3: 에라토스테네스의 체 (여러 수에 대해 소수 판별)

소수인지 여부를 하나씩이 아닌 범위 내의 모든 수에 대해 빠르게 판별할 때 사용하는 방법입니다. 특정 수까지의 소수를 한 번에 구하고 싶을 때 유용합니다.

function sieveOfEratosthenes(limit) {
  const primes = Array(limit + 1).fill(true);
  primes[0] = primes[1] = false;

  for (let i = 2; i * i <= limit; i++) {
    if (primes[i]) {
      for (let j = i * i; j <= limit; j += i) {
        primes[j] = false;
      }
    }
  }

  return primes
    .map((isPrime, index) => isPrime ? index : null)
    .filter((v) => v !== null);
}

console.log(sieveOfEratosthenes(30)); // [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

장점: 수의 범위가 클 때 매우 효율적
단점: 메모리 사용량이 많을 수 있음

관련글: 2016.05.17 - [Programing/Algorithm] - 에라토스테네스의 체를 이용한 소수 찾기

---

시간 복잡도 비교

방법	시간 복잡도	사용 상황
2부터 n-1까지 나누기	O(n)	단순한 구조, 소수 개별 판단
√n까지 나누기	O(√n)	성능 향상된 개별 소수 판별
에라토스테네스의 체	O(n log log n)	여러 수를 동시에 소수 판별할 때

---

마무리 및 추천 자료

소수 판별은 수학적 개념을 프로그래밍으로 옮기는 연습에 매우 적합한 주제입니다. 구현 방식에 따라 성능이 크게 달라지므로 상황에 맞는 알고리즘 선택이 중요합니다. 한 개의 수인지, 여러 수인지, 수의 크기가 얼마나 되는지에 따라 가장 효율적인 접근을 선택하는 습관을 길러야 합니다.

소수 관련 알고리즘 문제 풀이에 도움이 되는 무료 리소스:

• 프로그래머스 알고리즘 강의
• LeetCode Prime Number Problems
• replit JavaScript 연습 환경

이 주제는 코딩 테스트에서 자주 등장하며, 숫자 처리에 자신감을 높여주는 중요한 기반이 됩니다.