백준 4948번

소수에 관한문제가 계속나와 이번에도 그전에 풀던 방식에서 조금만 바꿔주면 쉽게 풀리는문제 인줄알고

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./inp.txt";
let inputs = fs.readFileSync(filePath).toString().trim().split("\n");
for (let i = 0; i < inputs.length; i++) {
  let M = Number(inputs[i]);
  let N = M * 2;
  let resultArr = [];
  for (let i = M; i <= N; i++) {
    let count = 0;
    for (let j = 1; j <= i; j++) {
      if (i % j === 0) {
        count++;
      }
    }
    if (count === 2) {
      resultArr.push(i);
    }
  }
  console.log(resultArr.length);
}

이런식으로 풀어보았는데 시간이 너무오래걸려서 다른방법을 찾아보니 에라토스테네스의 체가 발견한 소수방법 이란 것 을알게되었다. 그래서 그방법을 사용하면

let fs = require('fs');
let inputs = fs.readFileSync('inp.txt').toString().trim().split('\n');
inputs.pop();

for (let i = 0; i < inputs.length; i++) {
   let input = Number(inputs[i]);

   let input2 = input * 2;

   let isPrimeNumber = Array(input2 + 1).fill(true);
   isPrimeNumber[0] = isPrimeNumber[1] = false;

   function PrimeNumber() {
       for(let i = 2; i <= Math.ceil(Math.sqrt(input2)); i++) {
           if(isPrimeNumber[i]) {
               let m = 2;
               while(i * m <= input2) {
                   isPrimeNumber[i * m] = false;
                   m++;
               }
           }
       } 
       let results = [];
   
       for(let i = input + 1; i <= input2; i++) {
           if(isPrimeNumber[i]) {
               results.push(i);
           }
       }
       console.log(results.length);
   
   }
   
   PrimeNumber();
}

이런식으로 빠르게 구할수 있다.