에라토스테네스의 체 - 소수 빠르게 알아내기

1~N 사이의 숫자중 소수를 구하는 문제가 있습니다.
이때

let num = [];
let N = 100;
for(let i =1; i<=N;i++){
	if(N%i !== 0) num.push(i);
}

아래의 방법을 통해 O(N)으로 구할 수 있습니다.

하지만 N이 커지면 커질수록 시간이 오래걸립니다.
그렇기 때문에 에라토스테네스의 체 방법으로 소수를 구하면 빠릅니다.

이 방법의 핵심은 n의 배수는 무조건 소수가 될 수 없다!

let N = 100;
let arr = [];
for(let i = 0;i<=N;i++){
	arr.push(i); //arr = [0,1,2,...,100]
}
arr[1] = 0; //1은 소수가 아니기 때문에
for(let i = 2; i<= N; i++){
	if(arr[i] === 0)continue;
    for(let j = i*2; j <= N ; j += i){
    	arr[j] = 0;
    }
}
arr.filter( x => x); //=> 소수만 남아있다.