Skip to main content

소수 찾기

Solution​

function solution(n) {
  const answer = new Set();

  for (let i = 2, num = i * i; num < n; i++, num = i * i) {
    if (!answer.has(i)) {
      for (let l = num; l <= n; l += i) {
        answer.add(l);
      }
    }
  }

  return n - (answer.size + 1);
}

Review​

아리스토텔레스의 체​

간단하게 1~100까지 숫자 중 소수를 찾는 가정

note
  1. 1 ~ 100 중에서 1 (소수, 합성수도 아닌 유일한 자연수 제거)
  2. 2(소수)를 제외한 2의 배수 제거
  3. 3(소수)를 제외한 3의 배수 제거
  4. 4는 1번에서 이미 지웠기에 5로 건너뛴다.
  5. 5(소수)를 제외한 5의 배수 제거
  6. 6는 1번에서 이미 지웠기에 5로 건너뛴다.
  7. 7(소수)를 제외한 7의 배수 제거
  8. 8, 9 이미 위에서 지웠기에 건너뛴다.
  9. 10 이상은 루트 100 했을 때 이미 그 이상의 숫자이기에 제외한다.
  10. 남은 숫자는 전부 소수이다.

References​