[JS] 백준 1929번 소수 구하기

 

출처

백준 온라인 저지

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

1929번: 소수 구하기

 

문제

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

 

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

반응형

풀이

주어진 입력 n ~ m의 범위 안에 존재하는 소수를 모두 찾아 반환하는 문제입니다.

 

이번 문제처럼 1,000,000까지의 큰 범위가 주어졌을 때는 에라토스테네스의 체 방식을 사용하는 것이 효율적입니다.

 

에라토스테네스의 체를 이용하여 2~m까지 각 숫자가 소수가 아닌 수를 찾아 객체에 선언해놓고, n ~ m까지 for문으로 소수가 아닌 수를 찾은 객체를 순회하면서 값을 찾아줍니다.

 

객체에서 값을 못 찾으면 소수라는 뜻이므로 출력, 값이 존재하면 소수가 아닙니다.

 

그리고 무엇보다 입력에서는 1도 입력이 될 수 있습니다.

여기서 하나 다시 확인해야하는 부분은 1은 소수가 아닙니다.

 

 

https://gurtn.tistory.com/103

[JS] 소수 판별하기

 

코드

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

const [n, m] = input.split(" ").map(v => Number(v));

const prime = { 1: true };

for (let i = 2; i <= Math.ceil(Math.sqrt(m)); i++) {
   if (prime[i]) {
      continue;
   }

   for (let j = i ** 2; j <= m; j += i) {      
      prime[j] = true;
   }
}

const results = [];

for (let i = n; i <= m; i++) {
    if (!prime[i]) {
        results.push(i);
    }
}

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