백준 2581번 JavaScript

백준 2581번 node.js 해결

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const [a, b] = input.map(Number);
const arr = [];
const primeCheck = number => {
  //number의 제곱근까지만 판별해도 소수 판별 가능
  for (let i = 2 ; i <=Math.sqrt(number); i+=1){
    if(number%i === 0){
      return false;
    }
  }
  return number;
}

//주어진 범위에서 소수인 것을 판별
for (let j = a ; j <= b ; j += 1 ){
  //구해야 하는 범위에 1이 포함 될 경우 배제(1은 소수가 아니므로)
  if(j!==1) arr.push(primeCheck(j));
}

//배열에서 false를 제외시킴
const filteredArr = arr.filter(isNum => isNum !==false);
const sum = filteredArr.reduce((a, b)=> a+b, 0);
const min = Math.min(...filteredArr);
if(filteredArr.length!==0) console.log(sum + '\n' + min);
else console.log(-1);  //소수가 없는 경우

기본적으로 소수는 2보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어 떨어지지 않는 자연수입니다.

어떤 자연수가 소수인지 아닌지 판별하기 위해서는 n을 2부터 n-1으로 나누어보고, 나머지가 0인 수가 하나라도 존재한다면 n은 소수가 아닌 것입니다. 시간 복잡도는 O(X)입니다.

간단하게 O(X)보다 더 빠르게 동작하게 할 수 있는데요.
자연수의 약수에는 특징이 있습니다.
16의 약수를 예시로 들어보겠습니다.

1, 2, 4, 8, 16

16은 4를 기준으로 하여 대칭을 이룹니다. (1x16, 2x8, 4x4)
이는 이 자연수가 소수인지를 판별할 때 2, 3, 4 만 확인하여 나누어 떨어지는지 확인하면 된다는 것입니다.
따라서 n의 제곱근, Math.sqrt(n)을 하면 시간복잡도O(X^0.5)에 소수를 판별할 수 있습니다.
간단한 처리법임에도 시간복잡도를 많이 개선할 수 있으므로 기억해두면 좋을 것 같습니다.

소수 문제는 몇 번 풀어봤음에도 1을 예외처리 하는 것을 잊어버려서 로직을 이해했는데도 정답을 받는 데 꽤 걸렸던 문제였습니다. 다른 문제에서는 항상 확인했던 부분입니다.
문제가 복잡해지더라도 예외처리를 꼼꼼하게 신경쓰는 습관을 들여야겠습니다.