[Baekjoon] 2581번 : 소수 문제풀이 (Node.js)

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

문제

자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최솟값을 찾는 프로그램을 작성하시오.

예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8개가 있으므로, 이들 소수의 합은 620이고, 최솟값은 61이 된다.

입력

입력의 첫째 줄에 M이, 둘째 줄에 N이 주어진다.

M과 N은 10,000이하의 자연수이며, M은 N보다 작거나 같다.

출력

M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다.

단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다.

코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const input = require('fs')
  .readFileSync(filePath)
  .toString()
  .trim()
  .split('\n');

const [M, N] = input.map(item => Number(item));
let primeNumbers = [];
let sum = 0;

for (let target = M; target <= N; target++) {
  for (let i = 2; i <= target; i++) {
    if (i * i > target) {
      primeNumbers.push(target);
      sum += target;
      break;
    }
    if (target % i === 0) {
      break;
    }
  }
}
if (primeNumbers.length === 0) {
  console.log(-1);
} else {
  console.log(sum);
  console.log(primeNumbers[0]);
}

풀이

어떤 소수도 N의 제곱근보다 큰 수로 나눠지지 않는다는 규칙이 있다.

위에 규칙을 적용해서 2부터 주어진 수에 -1 까지 나누어 주면서

• 주어진 수가 나누는 수에 제곱보다 작을 경우 주어진 수는 소수가 된다.
• 나머지가 0이 나올 경우 소수가 아니게 된다.

만약 primeNumbers에 아무 값도 없다면 -1을 출력하고
그렇지 않다면 첫줄에 합을, 두번째 줄에 가장 작은 소수를 출력하면 된다.