[백준] JavaScript 1978번 소수 찾기

Question

[백준] JavaScript 1978번 소수 찾기

input

첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

output

주어진 수들 중 소수의 개수를 출력한다.

example

4
1 3 5 7

3

Solution 1 (가장 원초적 방법)

2부터 판별하려는 수 전까지 나눠보고 나머지가 0이 안나오면 소수로 판정한다.
해당 수까지 모두 확인해야하므로 시간복잡도는 O(N)이 된다.

console.log(require('fs').readFileSync('/dev/stdin').toString().trim().split(/\s+/).slice(1).map(Number).filter(x=>{
    if(x===1) return;
    for(let i=2;i<x;i++){
        if(x%i===0) return;
    }
    return true;
}).length)

Solution 2 (개선된 방법)

해당 숫자의 √N 까지만 확인하는 방법이다. 예를 들어, 80의 약수를 보면 아래와 같다.

√80의 값은 약 8.xx로 이 값이 약수들의 중간값이 된다. 이 원리를 이용해 2부터 √N의 값까지 검사하게 된다면 이후의 값은 확인할 필요가 없게 되고, 시간복잡도는 O(√N)이 된다.

코드의 가독성을 위해 Math.sqrt(x)가 아닌 i의 제곱값으로 확인한다.

console.log(require('fs').readFileSync('/dev/stdin').toString().trim().split(/\s+/).slice(1).map(Number).filter(x=>{
    if(x===1) return;
    for(let i=2;i*i<=x;i++){
        if(x%i===0) return;
    }
    return true;
}).length)

Reference

https://myjamong.tistory.com/139