[JavaScript] 1929 | 백준 (에라토스테네스의 체)

📄 문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

---

⌨ 예제 입력

3 16

📺 예제 출력

3
5
7
11
13

---

🚩solution

시간 초과가 계속 나와서 구글링을 좀 해봤다...!
소수 구하는 시간 복잡도가 제일 빠른걸 찾아 보았더니
'에라토스테네스의 체'라는 알고리즘을 알게 되었다!
동작 원리는 제일 작은 소수 2부터 시작한다.
2를 제외한 2의 배수는 소수가 아니다.
다음 소수 3
3을 제외한 3의 배수는 소수가 아니다.
이런식으로 소수의 배수들을 배제하는 방식인 것이다.
자세한 것은 참조에 링크 달아 두겠습니다.

const input = require('fs')
  .readFileSync('/dev/stdin')
  .toString()
  .trim()
  .split(' ');
const [M, N] = [Number(input[0]), Number(input[1])];

let arr = Array(N + 1).fill(true);

arr[0] = arr[1] = false;

for (i = 2; i <= Math.sqrt(N); i++) {
  if (!arr[i]) continue;
  for (j = 2; i * j <= N; j++) {
    arr[i * j] = false;
  }
}

for (i = M; i < arr.length; i++) {
  if (arr[i]) console.log(i);
}

---

[에라토스테네스의 체]
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