소수 구하기 (에라토스테네스의 체)

소수를 구하기 위한 알고리즘으로 에라토스테네스의 체가 있다.

2부터 시작하여 2의 배수들을 지워나가고, 그 다음엔 3의 배수, 그 다음엔 5의 배수 (4는 2의 배수로 이미 소수 후보에서 제외되었다)를 지워가며 소수를 추려내는 방법이다.

const eratos = (n) => {
  const arr = new Array(n + 1).fill(true);
  arr[0] = false;
  arr[1] = false;
  for(let i = 2; i <= Math.sqrt(n); i++) {
    for(let j = i*i; j <= n; j += i) {
      arr[j] = false;
    }
  }
  const answer = [];
  for(let i = 2; i <= n; i++) {
    if(arr[i]) {
      answer.push(i);
    }
  }
  return answer;
}

배수를 확인할 숫자는 n의 제곱근까지만 확인하면 된다.

arr[j]가 false가 아닌 index는 소수이므로, 배수를 제거할 땐 j*j부터 제거한다.

작업이 끝나고, 2 이상이면서 true인 index는 소수이다.

 

 

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전