백준 - 소수찾기(에라토스테네스의 체)

문제

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

입력

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

출력

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

예제 입력 1

4
1 3 5 7

예제 출력 1

3

제출

let fs = require('fs');
let inputs = fs.readFileSync('/dev/stdin').toString().split('\n');
let num = inputs[1].split(' ').map(Number);
var answer = 0;
for(let i=0; i<num.length; i++){
    if(num[i] === 1){
        continue;
    }else{
        var count = 0;
        for(let j=2; j<num[i]; j++){
            if(num[i]%j === 0){
                count++;
            }
        }
        if(count === 0){
            answer++;
        }
    }
}
console.log(answer)

입력의 양이 그렇게 많지 않아서 이렇게 구현하긴 했지만

딱봐도 너무 많이 반복을 하는게 보인다

그래서 더 나은 알고리즘이 있을 거라 생각해서 찾아봤다

역시나 천재는 많았고 그 천재는 아주 예전부터 존재했다

에라토스테네스라는 사람이 생각한 방법은 아래와 같다

소수는 약수가 1과 자기 자신뿐인 수를 의미한다

n까지 숫자중에 소수의 개수를 파악한다고 해보자

그렇다면 1부터 루트n까지의 수의 배수들을 모두 삭제하고 남는 것들이 소수이다

처음엔 이해가 가지않았다

n을 100이라고 하겠다

1은 소수가 아니니 제외를 하고 2의 배수들을 모두 삭제한다

이후 3의 배수또한 삭제한다

4는 2의 배수이기때문에 이미 삭제되었다

5의 배수도 삭제한다

6도 3의 배수였기에 이미 삭제되었다

7의 배수도 삭제한다

8 9 10도 이미 전 숫자들의 배수이기 때문에 삭제되었다

그 이상의 수들은 이미 전의 수들의 배수이기에 삭제되었거나

소수라서 삭제되지 않았다

남은 것들의 개수가 즉 소수의 개수인 것이다

여기에 그림으로 잘 설명이 되어 있다

이런식으로 삭제를 하면 볼 것도 많이 없고 반복도 제곱근까지만 돌면 되기때문에

현존하는 소수를 찾는 알고리즘중 가장 빠르다고 한다

역시 천재는 많고 많다