1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
소수는 1과 자기 자신으로만 나누어 지는 수를 의미합니다.(1은 소수가 아닙니다.)
function solution(n) {
let count = 0;
for (let i = 2; i <= n; i++) {
let 소수 = true;
for (let j = 2; j < i; j++) {
if (i % j === 0) {
소수 = false;
}
}
if (소수) ++count;
}
return count;
}
function solution(n) {
const 소수들 = [2];
for (let i = 2; i <= n; i++) {
const is소수 = 소수들.some((c) => i % c === 0);
if (!is소수) 소수들.push(i);
}
return 소수들.length;
}
function solution(n) {
const 소수들 = new Array(n).fill(true);
소수들[0] = false;
for (let i = 2; i ** 2 <= n; i++) {
if (소수들[i - 1] === true) {
for (let j = i ** 2; j <= n; j += i) {
소수들[j - 1] = false;
}
}
}
return 소수들.filter((e) => e).length;
}
//위와 같은 원리
function solution(n) {
const s = new Set();
//짝수는 소수 일수가 없음
for (let i = 3; i <= n; i += 2) {
s.add(i);
}
s.add(2);
for (let j = 3; j ** 2 < n; j++) {
if (s.has(j)) {
for (let k = j ** 2; k <= n; k += j) {
s.delete(k);
}
}
}
return s.size;
}
에라토스테네스의 체 라는 것을 이해해야 하는 수학적 문제이다.
소수를 구하기보다는 소수가 아닌 것을 제외하면 되고 그건 소수들의 배수를 제거하면 된다.