[JS] 1929

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : './data.txt';

const input = fs
  .readFileSync(path)
  .toString()
  .trim()
  .split(' ')
  .map((x) => Number(x));

function solve(input) {
  const M = input.shift();
  const N = input.shift();

  const arr = [...new Array(N + 1).keys()]; // 0부터 N까지 배열 생성

  for (let i = 2; i <= Math.sqrt(N); i++) {
    // 2부터 N의 제곱근까지에 대해서
    if (arr[i]) {
      // arr[i]의 값이 곧 i
      for (let j = i * i; j <= N; j += i) {
        arr[j] = false; // i=2일 때, 4부터 2의 배수들이 false가 됨, 이후 i=3일 때는 9부터(왜냐하면 앞에서 이미 이전 소수인 2에 의해 값들이 걸려졌기 때문)
      }
    }
  }

  arr.shift(); // 배열에서 0 값 제거
  arr.shift(); // 배열에서 1 값 제거

  for (let value of arr.filter((x) => x >= M)) {
    // 배열에서 M보다 큰 애들만 남게 만들기
    value ? console.log(value) : null; // value가 true일 땐 console.log(value), false일 땐 null
  }
}

solve(input);

 

백준

1929번: 소수 구하기

 

에라토스테네스의 체 : 나무위키

에라토스테네스의 체 - 나무위키

 

개인적으로 위키피디아도 좋지만, 전반적인 개념을 나무위키에서 더 쉽게 설명하는 것 같아 첨부한다.
말그대로 체로 거르듯이 소수가 아닌 숫자들을 필터링하는 개념이다.
여기서 중요한 핵심!

1. a에서 b까지 소수를 찾는다고 할 때, 나눠서 체크해야하는 값은 b의 제곱근보다 클 수 없다.
2. 처음 첫번째 소수로 나눌 때, 해당 소수의 제곱부터 시작하면 된다는 점.
   (자세히 생각해보면 먼저 2로 나눌 때 - 2의 제곱인 4부터 시작해서 2의 배수들은 다 false가 되고 이후 3으로 할 땐, 굳이 6을 처리할 필요가 없다. 이미 다 2에서 걸러짐, 마찬가지로 다음 5일 때도 10, 15, 20은 이미 다 걸러짐. 즉 5의 제곱인 25부터 시작하면 된다.