[알고리즘] 에라토스테네스의 체(소수 판별)

소수 판별 알고리즘으로 n까지의 소수를 구하고 싶다면 자기 자신을 제외한 소수의 배수를 지워나가는 방법을 의미합니다.

function primeNumberSieve(n) {
  const area = new Array(n + 1).fill(false);
  const result = [];

  for (let i = 2; i <= n; i++) {
    if (area[i]) continue;

    for (let j = i * 2; j <= n; j += i) {
      area[j] = true;
    }
  }

  area.forEach((flag, index) => {
    if (index > 1 && !flag) {
      result.push(index);
    }
  });

  return result;
}

const result = primeNumberSieve(10);
console.log(result);
// [2, 3, 5, 7]

 

위 알고리즘은 배열의 크기 때문에 메모리 문제가 발생할 수 있습니다. 이 경우 해당 수를 소수인지 확인하는 함수를 사용해야 합니다.

function isPrime(num) {
  if(num == 0 || num == 1) return false;
  if(num == 2) return true;
  if(num % 2 == 0) return false;
  
  // Math.sqrt(num)까지만 반복문을 동작해도 되는 이유
  // num이 합성수인 경우 A * B의 형태로 나타낼 수 있다. (단, A >= B)
  // A^2 >= A*B  >>> A^2 >= n >>> A >= n^(1/2)
  // A >= n^(1/2) >= B
  // 따라서 A의 최솟값 = B의 최댓값 = n^(1/2)이기 때문에 Math.sqrt(num)까지만 동작하면 된다.
  for(let i = 3; i <= Math.sqrt(num); i++) {
    if(num % i == 0) return false;
  }
  
  return true;
}

 

참고

어떤 수가 소수인지 아닌지 판별하는 다양한 알고리즘, KKH, 2024.11.15