[Algorithm] 소수구하기

문제

N이 주어졌을 때, N보다 크고 2N보다 작거나 같은 소수의 개수를 구하는 문제

풀이

에라토스테네스의 체

0 ~ 2N까지의 숫자에 해당하는 배열을 생성하고 에라토스테네스의 체 를 이용하여 소수를 구하려고 한다.
이 방법은 2부터 구하고자 하는 숫자까지를 모두 나열하고 2부터 차례대로 1씩 증가하면서 해당 숫자의 배수를 모두 지우는 방식이다.

 

그렇기 때문에 코드에서는 배열의 index를 활용해서 true -> false로 변경시켰다.
이 때 해당 수의 제곱근 까지만 범위를 제한하게되면 루프횟수를 O(logN)으로 만들어 줄 수 있다.

 

제곱근 의 법칙이 성립하는 이유는 어떤 수(n)은 두 수 (a, b)의 곱으로 나타낼 수 있다.
예를 들어 12는 2 * 6, 3 * 4로 나타낼 수 있고 두가지 경우의 작은 수를 보게되면 2, 3 이다.
이 작은수로 어떤 수(n)을 나누게 되면 두가지 경우의 큰 수(6, 4)를 알 수 있게 된다. 즉 작은 수만 가지고도 큰 수를 알 수 있게 된다는 것이다.

코드

require("readline")
  .createInterface(process.stdin, process.stdout)
  .on("line", (line) => {
    input = Number(line.trim());
  })
  .on("close", () => {
    console.log(solution(input));
  });

let input;

let solution = (n) => {
  let num = n * 2;
  let arr = Array(num + 1)
    .fill(true)
    .fill(false, 0, 2);

  for (let i = 2; i ** 2 <= num; i++) {
    if (arr[i]) {
      for (let j = i ** 2; j <= num; j += i) {
        arr[j] = false;
      }
    }
  }
  const result = arr.filter((ele, index) => ele && index >= n + 1).length;
  return result;
};