[300] 1929번 소수 구하기

1929번 소수 구하기

문제

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

입력

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

출력

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

예제 입력 1 복사

3 16

예제 출력 1 복사

3
5
7
11
13

코드

//---- 세팅 ----//
const fs = require('fs');
const stdin = (
  process.platform === 'linux'
    ? fs.readFileSync('/dev/stdin').toString()
    : `\
3 16
`
).split('\n');

const input = (() => {
  let line = 0;
  return () => stdin[line++];
})();

//---- 풀이 -----//

const [start, end] = input().split(' ').map(Number);

const numberArr = [...Array(end - start + 1)].map((v, i) => i + start);

const isPrime = n => {
  if (n <= 1) return false;
  for (let i = 2; i <= n / i; i++) {
    if (n % i === 0) return false;
  }
  return true;
};

const primeArr = numberArr.filter(n => isPrime(n));

console.log(primeArr.join('\n'));

풀이

소수 : 1과 자기 자신만을 약수로 갖는 수

반복문 범위

• n의 약수는 n의 절반을 넘길수 없다. i <= n / 2

• i * i <= n , i <= Math.sqrt(n) , (훨신 더 빠른다.)

소수 여부를 검사할 수에 대해서 그 값의 제곱근을 기준으로 그 곱은 대칭적으로 곱이 일어나므로 제곱근 이하의 작은 값까지만 검사를 하면 나머지는 검사를 할 필요가 없다는 방법으로 검사할 데이터를 제곱근 개 이하로 줄 일 수 있는 방법입니다.

출처: https://www.it-note.kr/308 [IT 개발자 Note]