[백준2960_자바스크립트(javascript)] - 에라토스테네스의 체

🔴 문제

에라토스테네스의 체

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const [n, k] = fs.readFileSync(path).toString().trim().split(' ').map(Number);
const map = Array(n + 1).fill(false);
let ans = 0;

exit : for (let i = 2; i <= n; i++) {
  if (map[i]) continue;

  for (let j = i; j <= n; j += i) {
    if (!map[j]) {
      map[j] = true;
      ans += 1;
    }
    
    if (ans === k) {
      console.log(j);
      break exit;
    }
  }
}

🟢 풀이

⏰ 소요한 시간 : -

에라토스테네스의 체 로직을 구현하는 문제다...!
문제에서 알고리즘에 대한 설명을 해줬기 때문에 그대로 구현하면 된다.
n까지의 배열을 만들고 2부터 n까지 반복하면서 아직 지우지 않은 작은수를 지우고 그 수의 배수를 지워주면 된다. 수를 지울 때마다 정답 ans를 1씩 증가하고, 이 수가k와 같다면 종료한다.

🔵 Ref