문제 이해하기
숫자 n을 첫 번째이자 유일한 인수로 받는 자바스크립트 함수를 작성해야 합니다. 이 함수는 2부터 n까지 범위 안에 있는 모든 소수(prime number)의 개수를 반환해야 합니다.
예를 들어 다음과 같습니다.
n = 10일 때, 출력 결과: 4 (2, 3, 5, 7) n = 1일 때, 출력 결과: 0
풀이 방법: 에라토스테네스의 체
이 문제는 에라토스테네스의 체(Sieve of Eratosthenes) 알고리즘을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 2부터 n-1까지의 숫자를 일단 모두 소수 후보로 표시합니다.
- 가장 작은 소수인 2부터 시작해, 각 수의 배수들을 모두 '소수 아님'으로 표시합니다.
- 배수 제거를 i²부터 시작하는 이유는, 그보다 작은 배수들은 이미 더 작은 소수들의 배수로 제거되었기 때문입니다.
- 마지막으로 남아 있는 소수의 개수를 세어 반환합니다.
예제 코드
const countPrimesUpto = (num = 1) => {
if (num < 3) {
return 0;
};
let arr = new Array(num).fill(1);
for (let i = 2; i * i < num; i++) {
if (!arr[i]) {
continue;
};
for (let j = i * i; j < num; j += i) {
arr[j] = 0;
};
};
return arr.reduce((a, b) => b + a) - 2;
};
console.log(countPrimesUpto(35));
console.log(countPrimesUpto(6));
console.log(countPrimesUpto(10));코드 동작 원리
코드의 흐름을 단계별로 살펴보겠습니다.
- 기저 조건 처리: num이 3보다 작으면 2 이상의 소수가 존재하지 않으므로 0을 바로 반환합니다.
- 배열 초기화: 길이가 num인 배열을 만들고 모든 요소를 1로 채웁니다. 여기서 1은 '소수 후보'를 의미합니다. 인덱스 0과 1은 실제 숫자 0과 1에 해당하며 소수가 아니므로, 최종 결과에서 2를 빼주어 보정합니다.
- 체로 걸러내기: 외부 반복문은 √num까지만 순회합니다(i * i < num). 내부 반복문은 i²부터 num 미만까지 i씩 증가하며 i의 배수를 모두 0으로 표시합니다.
- 개수 계산: reduce() 메서드로 배열의 모든 값을 합산한 뒤 2를 빼서, 2부터 n-1 사이의 실제 소수 개수를 반환합니다.
실행 결과
콘솔에 출력되는 결과는 다음과 같습니다.
11 3 4
- 35 이하: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 → 총 11개
- 6 이하: 2, 3, 5 → 총 3개
- 10 이하: 2, 3, 5, 7 → 총 4개
마무리
단순히 각 숫자마다 나눗셈으로 소수 여부를 검사하는 방식은 O(n√n)의 시간 복잡도를 가지지만, 에라토스테네스의 체를 사용하면 O(n log log n)으로 크게 개선할 수 있습니다. 입력 범위가 커질수록 두 방식의 성능 차이는 더욱 벌어지므로, 소수 개수를 대량으로 계산해야 하는 상황에서는 체 알고리즘이 가장 좋은 선택입니다.