[boj] 1929. 소수 구하기 (node.js)

요약

소수 구하기 - 에라토스테네스의 체
두 수 n과 m이 주어질 때, n이상 m이하의 모든 소수를 출력하라.

코드

// const fs = require("fs");
// const filePath = process.platform === "linux" ? "dev/stdin" : "input.txt";
// const stdin = fs.readFileSync(filePath).toString().split("\n");

// let cnt = 0;
// const input = () => {
//   return stdin[cnt++];
// };

const solution = () => {
  const [m, n] = input()
    .split(" ")
    .map((x) => parseInt(x));
  const arr = new Array(n + 1).fill(1, 2, n + 1);
  for (let i = 2; i <= n; i++) {
    if (arr[i]) {
      for (let j = i * i; j <= n; j += i) {
        arr[j] = 0;
      }
    }
  }
  const result = [];
  for (let i = m; i <= n; i++) {
    if (arr[i]) {
      result.push(i);
    }
  }
  console.log(result.join("\n"));
};

// solution();

• 특정 수가 소수일 때, 그 수를 제외하고 그 수의 배수는 모두 체로 걸러진다. 체로 걸려졌는지의 여부를 판단하기 위해 크기가 (n+1)인 배열을 만들고 초기값으로 모두 1을 저장한다.
• 예를 들어, 2의 경우 4, 6, 8, ... 을 모두 체로 거르고 -> 그 다음 수인 3부터 다시 시작해서 걸러지지 않은 수인 9, 15, ... 을 거르는 식이다. 이때 주의해야 할 점이 그 수는 남겨둬야 한다 는 점이다. 아래처럼 코드를 짜면 된다.

  for (let i = 2; i <= n; i++) {
      if (arr[i]) {
        for (let j = i * i; j <= n; j += i) {
          arr[j] = 0;
        }
      }
    }

• DFS 처럼 작동하나, j = i * i 로 가령 i == 3인 경우는 j = 9부터 시작하기 때문에 계산량을 줄일 수 있다.