[백준 / BOJ] 4948번 베르트랑 공준 (Javascript / Node js)

https://www.acmicpc.net/problem/4948

4948번: 베르트랑 공준

 

 

문제 해석

이 문제는 에라토스테네스의 체를 이용해서 소수들이 검사되어 있는 배열을 생성해주는 메소드를 만들어주고,

 

함수의 인자로 배열의 크기(2N), 검사할 수의 시작 인덱스(M)를 인자로 받아 반복문을 통해 해당 범위내의 소수의 수를 세준 뒤 return해주면 되겠다. 

 

 

에라토스테네스의 체를 이해하기 위해서는 아래 링크를 참고해주시면 감사하겠습니다.

 

[백준 / BOJ] 1929번 소수 구하기 (Javascript / Node js) (tistory.com)

[백준 / BOJ] 1929번 소수 구하기 (Javascript / Node js)

 

 

전체코드

 

const fs = require("fs");

const input = fs

  .readFileSync("../input.txt")

  .toString()

  .trim()

  .split("\n")

  .map((item) => Number(item));

input.pop();

const Eratos = (M, N) => {  //에라토스테네스의 체 메소드

  var arr = [];

  arr[0] = false;

  arr[1] = false;

  for (let i = 2; i <= N; i++) { 

    arr.push(true);

  }

  for (let i = 2; i * i <= N; i++) {

    if (arr[i]) {

      for (let j = i * i; j <= N; j += i) {

        arr[j] = false;

      }

    }

  }

  let cnt = 0;

  for(let i = M; i< arr.length; i++){

    if(arr[i]){

       cnt++;

    }

  }

  return cnt;

};

let answer = [];

for(let i=0; i<input.length; i++){

    answer.push(Eratos(input[i] + 1, input[i]*2));

}

console.log(answer.join("\n"));

 

 

이번 문제는 지난번 풀었던 소수 구하기와 너무 유사하여 글을 쓸지 말지 고민됐지만, 이렇게 몇 자라도 적으며 한번이라도 더 알고리즘을 복기하고자 포스팅했다. 이제 에라토스테네스의 체는 확실하게 활용할 수 있을 것 같다.