백준 1929번 :: 주어진 범위 안에서 소수 찾기

[백준 1929번 소수 구하기]

문제

시간 제한 2초, 메모리 제한 256MB

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

풀이 방법

1. 주어진 범위에 해당하는 값들이 담긴 배열을 만든다.

배열의 길이 : 끝 값 - 처음 값 +1

2. 처음 값부터 1씩 증가하며 소수인지 검증한다.

valid: 소수 여부. 초깃값은 true, 소수가 아니면 false로 바꾼다.

3. 검증할 숫자를 2부터 1씩 증가하며 나누었을 때 나머지가 존재하는지 확인한다.

나머지가 존재하지 않으면(0이면) 소수가 아니므로 valid를 false로 바꾸고 반복문을 종료한다.

4. 3은 검증할 숫자의 제곱근까지만 나누어본다.

2부터 제곱근까지 1씩 증가하며 나누어보았을 때, 나누어떨어지는 경우가 없다면 더 검증해볼 필요 없이 소수이다!!

👉🏻 이렇게 하지 않으면, 시간 초과 혹은 메모리 초과가 뜬다ㅠ_ㅠ

const fs = require("fs");
const input = fs
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split(" ")
  .map((el) => Number(el));

const result = [];
new Array(input[1] - input[0] + 1).fill(input[0]).forEach((el, i) => {
  const num = el + i;
  let valid = true;
  for (let j = 2; j * j <= num; j++) {
    if (num % j === 0) {
      valid = false;
      break;
    }
  }
  // 1은 소수가 아니므로 제외한다.
  if (valid && num !== 1) result.push(num);
});
result.forEach((el) => {
  console.log(el);
});