[백준 / 1929 / nodejs] 소수구하기 javascript

소수 구하기 문제는 에라토스테네스의 체를 쓰거나 범위의 제곱근까지만 비교해서 찾는 방식이 대부분인 것 같아서 둘 다 해봤다.

1. 2~ 제곱근까지 나눠보기

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const isPrime = (num) => {
    if(num === 1) return false;
    for(var i=2; i<=Math.sqrt(num); i++){
        if((num%i)==0) return false;
    }
    return true;
}

const [n,m] = input.shift().split(' ').map(e=>parseInt(e));

for(var i=n; i<=m; i++) 
    isPrime(i) ? console.log(i) : null;

isPrime함수에서 Math.sqrt를 쓴 이유는 제곱근을 기준으로 대칭적으로 곱이 일어나므로 수행시간을 단축시킬 수 있다.

1의경우 소수가 아니므로 별도로 조건문을 걸어줬고, 

문제에서는 M~N 범위를 구하는 걸로 했지만 나는 헷갈려서 N~M으로 해놓고 풀이했다.

 

n~m 까지 isPrime에 넘겨서 소수인지 판단했다.

2부터 num의 제곱근까지의 값으로 나눠서 나누어 떨어지는 것이 있으면 소수가 아닐 것이다. 소수는 1과 자기 자신으로만 나눠지니까

그래서 그런 값을 발견하면 바로 return false;

 

2. 에라토스테네스의 체

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const [n,m] = input.shift().split(' ').map(e=>parseInt(e));
const arr = Array.from(Array(m+1).keys())
for(let i=2; i<=Math.sqrt(m); i++){
    if(arr[i])
        for(let j = i*i; j<=m; j+=i)
            arr[j] = false;
}
arr.splice(0,2,false,false)
for(let i = n; i<=m; i++){
    if(arr[i]) console.log(arr[i])
}

2부터 끝숫자의 제곱근까지 보며 값이 있으면 그 값을 제외하고 그값의 배수들을 모두 false 시킨다.