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

소수?

1과 자신만으로 나누어 떨어지는 1보다 큰 양의 정수를 뜻한다.

내가 알던 이전의 소수 구하는 방법

n의 제곱근 (√n) 까지만 계산하기

function isPrime(num) {
  if (num === 1) return false;
  // 소수 판별법 - 약수를 구한다 생각하고 1과 자기 자신을 제외했을 경우 값이 있으면 약수가 존재하니깐, 소수가 아닌 것이다.
  for (let i = 2; i <= parseInt(Math.sqrt(num)); i++) {
    if (num % i === 0) return false;
  }
  return true;
}

에라토스테네스의 체? (GOOOOD!!!)

2부터 n까지의 자신을 제외한 배수를 제거하다 보면 소수만 남는다는 원리

function isPrime(num) {
  // 소수를
  let arr = Array(num + 1)
    .fill(true)
    .fill(false, 0, 2);

  for (let i = 2; i * i <= num; i++) {
    if (arr[i]) {
      for (let j = i * i; j <= num; j += i) {
        arr[j] = false;
      }
    }
  }
  return arr.filter((e) => e).length;
}

참고: https://ssafy-story.tistory.com/28