[백준] 1929 소수 구하기 / JS

문제

M과 N 사이의 소수를 구하는 문제!
단순히 해당 수보다 작은 2부터 시작해서 자기 자신의 수까지 나눠서 소수인지 판별할 수 있지만, 그렇게 푼다면 시간 초과가 날 수밖에 없다.

그러므로 에라토스테스의 체를 이용하여 문제를 풀어야 한다.

시간 초과된 코드
이 코드에선 1을 소수에서 제외시키는 부분이 없다. 이 부분을 간과했었다.

const input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split(" ").map(Number);
console.log(input);

const answer = [];

for (let i = input[0]; i<= input[1]; i++){
  for (let j=2; j <= i; j++){
    if (j !== i && i % j === 0){
      break
    }
    else if (j === i && i % j === 0) {
      answer.push(i)
    }
  }
}

console.log(answer.join('\n'))

에라토스트테네스를 이용한 풀이에서는 두번이나 틀린 이유를 몰랐었다. 1을 소수에서 제외시키는 부분을 적지 않아서 틀린 것이었다.

다음에 풀 때는 코드를 찾아보지 않고 풀어봐야겠다!

const input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split(" ")
  .map(Number);

const n = 1000000;
const array = Array(n+1).fill(1);
const answer = [];

for (let i = 2; i <= Math.sqrt(input[1]) + 1; i++) {
  if (array[i] === 1) {
    let j = 2;
    while (i * j <= n) {
      array[i * j] = 0;
      j++
    }
  }
}

for (let i = input[0]; i <= input[1]; i++) {
  if (i === 1) continue
  if (array[i] === 1) {
    answer.push(i)
  }
}

console.log(answer.join('\n'))