에라토스테네스의 체

정수론

2020-12-21

체로 치듯이 수를 걸러내 소수를 찾는 방법

function sieveOfEratosthenes(n) {
  const answer = [...Array(n + 1).keys()];
  for (let i = 2; i < answer.length; i++) {
    if (answer[i] !== -1) {
      for (let index = i * i; index <= n; index += i) {
        answer[index] = -1;
      }
    }
  }

  return answer.filter(number => number !== -1 && number !== 0 && number !== 1);
}

입력

const n = 100;

출력

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]