백준 js 4948번

 

<문제>

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

 

 

 

 

<문제 핵심>

1. 에라스토텔레스의 체

개념: 소수를 판별하는 알고리즘으로 소수들을 대량으로 빠르고 정확하게 구하는 방법이다. 에라토스테네스의 체는 가장 먼저 소수를 판별할 범위만큼 배열을 할당하고 인덱스에 해당하는 값을 비교하여 범위에 해당하는 소수를 빠르게 찾아낸다. 즉 소수의 배수를 제거하여 소수가 아닌 것들을 제거하고 소수로만 구성되어 있는 배열을 만들 수 있다.

 

 

<문제 풀이과정 및 순서도>

1. 입력받은 후 inputs의 마지막 요소인 0을 제거한다.

let inputs = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
  .toString()
  .trim()
  .split("\n")
  .map(Number);

inputs.pop(); // 0 제거

 

 

2. 에라토스테네스의 체 알고리즘을 한 번만 실행하여 모든 테스트케이스의 소수를 미리 계산하기 위해서 inputs 배열 중 최대값을 선택하고 *2배 만큼의 범위를 설정한다. 여러번 모든 소수를 계산하는 것이 아닌 한 번에 모든 소수를 계산하는 것이다. 이후 설정한 범위만큼 배열을 채우고 0과 1은 소수가 아니기 때문에 false로 설정한다.

let maxInput = Math.max(...inputs);
let maxRange = maxInput * 2;
//예를 들어 입력값이 30인 경우 -> 60까지의 소수임을 판별하는 배열 생성
let isPrimeNumber = Array(maxRange + 1).fill(true);
isPrimeNumber[0] = isPrimeNumber[1] = false;

 

3. 2부터 시작하여, 해당 숫자가 소수인지 확인한다. 그 숫자가 소수라면, 그 숫자의 배수를 모두 제거한다.

 

for (let i = 2; i <= Math.ceil(Math.sqrt(maxRange)); i++) {
  if (isPrimeNumber[i]) {
    for (let j = i * i; j <= maxRange; j += i) {
      isPrimeNumber[j] = false;
    }
  }
}

 

4. input + 1부터 input * 2까지의 범위를 순회하는데 즉 각 숫자마다 범위에 맞춰서 소수가 있는지를 판단하고 있으면 count를 증가시켜준다. 이후 모든 입력값에 대한 순회를 마친 후 줄바꿈을 적용하며 출력한다.

let results = inputs.map((input) => {
  let count = 0;
  for (let i = input + 1; i <= input * 2; i++) {
    if (isPrimeNumber[i]) {
      count++;
    }
  }
  return count;
});

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

<전체 코드>

let inputs = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
  .toString()
  .trim()
  .split("\n")
  .map(Number);

inputs.pop(); // 0 제거

let maxInput = Math.max(...inputs);
let maxRange = maxInput * 2;

//예를 들어 입력값이 30인 경우 -> 60까지의 소수임을 판별하는 배열 생성
let isPrimeNumber = Array(maxRange + 1).fill(true);
isPrimeNumber[0] = isPrimeNumber[1] = false;

for (let i = 2; i <= Math.ceil(Math.sqrt(maxRange)); i++) {
  if (isPrimeNumber[i]) {
    for (let j = i * i; j <= maxRange; j += i) {
      isPrimeNumber[j] = false;
    }
  }
}

let results = inputs.map((input) => {
  let count = 0;
  for (let i = input + 1; i <= input * 2; i++) {
    if (isPrimeNumber[i]) {
      count++;
    }
  }
  return count;
});

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