에라토스테네스의 체 -javascript

에라토스테네스의 체

1을 제외하고 2부터 순차적으로 N까지 자신을 제외하고 자신의 배수들을 차례대로 지워가면 결국에는 소수들만 남는다는 원리이다. 여기서 N까지가 아니라 √N까지만 검사해도 결과는 같다.

예를 들어 N = 16 일 때를 생각해보자.

1은 소수가 아니니까 1은 제외하고 2부터 실행한다.
2는 자신을 제외한 2의 배수를 모두 제거한다.
[4,6,8,10,12,14,16] 를 모두 삭제한다.

다음은 3이다. 3을 제외한 3의 배수를 제거한다.
[6,9,12,15]를 삭제한다.(12는 이전에 삭제)

4는 이미 삭제되었다.

다음은 5이다. 5를 제외한 5의 배수를 삭제한다.
[10,15] 모두 이미 삭제되었다.
10은 5의 배수이면서 2의 배수이다.
15는 5의 배수이면서 3의 배수이다.
즉, 5의 배수는 25(5의 제곱)가 나오기 전까지 모든 5의 배수는 이미 삭제되었다.

따라서 √16(4)까지만 검사하면 된다. √16(4) 이후의 배수들은 이미 삭제되어 있기 때문에 신경 쓸 필요가 없다.

코드 구현 아이디어
1부터 N까지 들어간 배열을 만든다. 2부터 √N까지 반복문을 돌면서 안에서 해당의 숫자의 배수들을 0으로 만든다.(자연수 처리를 위해서 i < √N 대신 i^2 < N를 이용했다) 이후에 1은 소수가 아님으로 shift()로 제거하고 filter를 이용해서 0의 숫자들을 모두 제거한다. 이렇게 만들어진 배열의 길이를 리턴하면 1부터 N까지의 소수 개수를 알 수 있다.

function solution(n) {
  let arr = [];
  for (let i = 1; i <= n; i++) arr.push(i);
  for (let i = 1; i * i < n; i++) {
    if (arr[i]) {
      let num = arr[i];
      for (let j = num * num; j <= n; j += num) {
        arr[j - 1] = 0;
      }
    }
  }
  let answer = arr.filter((number) => number);
  answer.shift();
  return answer.length;
}

출처 사이트