2부터 타겟 숫자까지 모든 숫자를 나열한다.(10이라면 2, ... , 10)
순회를 시작하면서, 숫자가 소수라면 그의 배수들을 모두 지운다.
단, 지울 때 소수인 숫자는 내버려둔다.
그렇게되면 최초 2를 시작으로, 3, 5, 7 등의 배수들이 지워진다.
// 타겟 숫자 n을 받으면
// n 까지 소수 갯수를 반환하는 함수
function isPrime(n) {
// index는 0부터 시작하니 n + 1 까지 생성
// arr는 해당숫자(인덱스)가 소수면 true, 아니면 false
const arr = new Array(n + 1).fill(true);
// 0, 1은 소수가 아니니 false 처리
arr.splice(0, 2, false, false);
// 2부터 순회를 시작하나, 제곱수부터는 순회를 하지 않음
// 어떤수의 제곱이다 === 이미 소수가 아니다
for(let i = 2; i ** 2 <= n; i += 1) {
// 만약 해당숫자가 소수라면, 그 숫자의 배수들을 제거할것임
if (arr[i]) {
// 제곱수부터 해당숫자만큼 더해줄것임
for(let j = i ** 2; j <= n; j += i) {
arr[j] = false;
}
}
}
// console.table(arr);
return arr.filter(el => el).length;
}