[백준 / BOJ] 1929번 소수 구하기 (Javascript / Node js)

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

1929번: 소수 구하기

 

문제 해석

이번 문제는 입력받은 M과 N 사이의 모든 소수들을 출력해주면 되는 아주 단순한 문제이다.

 

소수를 구하면 되니 에라토스테네스의 체를 이용하면 매우 효율적으로 구할 수 있다.

 

에라토스테네스의 체에 관해서는 이전 [소수 찾기] 문제에서 다룬적이 있다.

그런데 바로 지난 문제인 [다음 소수]를 풀며 깨달은 점은 내가 소수 찾기 문제에서 사용했던 에라토스테네스의 체는 반쪽짜리도 안되는 알고리즘이었다는 것이다.

 

그 이유는 에라토스테네스의 체의 장점은 검사할 약수의 개수를 비약적으로 줄이는 것에 있는데 예전 소수 찾기 문제 풀이 포스팅에서는 이를 활용하지 않고 에라토스테네스의 체라며 우긴 꼴이였다.

 

에라토스테네스의 정의에 관해서는 아래 [소수 찾기]와 [다음 소수] 포스팅을 읽고 오면 이해할 수 있을 것이다.

[백준/BOJ] 1978번 소수 찾기 (Javascript/Node js)

 

[백준 / BOJ] 4134번 다음 소수 (Javascript / Node js)

 

전체 코드

const fs = require("fs");

const input = fs.readFileSync("../input.txt").toString().trim().split("\n").map(item => Number(item));

input.shift();

const prime = (n) => {
    if(n < 2){
        return false;
    }
    for(let i=2; i<= Math.sqrt(n); i++){ // i * i < n 으로 범위를 잡는 대신 i < sqrt(n) 으로 범위를 잡았다
        if(n % i == 0){
            return false;
        }
    }
    return true;
}

let answer = [];

for(let i of input){
    while(!prime(i)){
        i++;
    }
    answer.push(i);
}

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

 

특히나 for문의 실행 범위에 대한 설명은 이전 포스팅 [다음 소수]에 자세히 나와있다.