문제 개요
JavaScript에서 하나의 숫자 n을 입력받아, 2부터 n까지의 모든 소수(Prime Number)를 배열 형태로 반환하는 함수를 작성해야 합니다.
예를 들어, 입력값이 n = 24라면 출력 결과는 다음과 같습니다.
const output = [2, 3, 5, 7, 11, 13, 17, 19, 23];
소수 판별의 기본 원리
소수란 1과 자기 자신 외에는 약수를 가지지 않는 1보다 큰 자연수입니다. 어떤 수가 소수인지 판별하려면 2부터 해당 숫자의 절반(또는 제곱근)까지의 값으로 차례대로 나누어 보고, 한 번이라도 나누어 떨어지면 소수가 아닌 것으로 판단할 수 있습니다.
구현 코드
먼저 주어진 숫자가 소수인지 확인하는 isPrime 함수를 작성하고, 이를 활용해 n 이하의 모든 소수를 수집하는 primeUpto 함수를 만듭니다.
const num = 24;
// 소수 판별 함수
const isPrime = num => {
let count = 2;
while(count < (num / 2) + 1){
if(num % count !== 0){
count++;
continue;
};
return false; // 나누어 떨어지면 소수가 아님
};
return true;
};
// n 이하의 모든 소수를 배열로 반환하는 함수
const primeUpto = num => {
if(num < 2){
return []; // 2 미만에는 소수가 없음
};
const res = [2];
for(let i = 3; i <= num; i++){
if(!isPrime(i)){
continue;
};
res.push(i);
};
return res;
};
console.log(primeUpto(num));
실행 결과
코드를 실행하면 콘솔에 다음과 같은 결과가 출력됩니다.
[ 2, 3, 5, 7, 11, 13, 17, 19, 23 ]
코드 동작 방식
- isPrime 함수: 2부터 num/2 + 1까지의 숫자로 차례대로 나누어 보며, 하나라도 나누어 떨어지면 false를 반환합니다. 끝까지 나누어 떨어지지 않으면 true(소수)를 반환합니다.
- primeUpto 함수: 입력값이 2보다 작으면 빈 배열을 반환하고, 그렇지 않으면 2를 초기값으로 설정한 뒤 3부터 n까지 반복하면서 소수로 판별된 숫자만 결과 배열에 추가합니다.
성능 개선: 에라토스테네스의 체
n의 값이 매우 커지면 위 방식은 각 숫자마다 반복적으로 나눗셈 검사를 수행해야 하므로 비효율적일 수 있습니다. 이런 경우 에라토스테네스의 체(Sieve of Eratosthenes) 알고리즘을 사용하면 훨씬 빠른 속도로 소수 목록을 얻을 수 있습니다.
const sieveUpto = num => {
if(num < 2) return [];
const sieve = new Array(num + 1).fill(true);
sieve[0] = sieve[1] = false;
for(let i = 2; i * i <= num; i++){
if(sieve[i]){
for(let j = i * i; j <= num; j += i){
sieve[j] = false;
};
};
};
return sieve.reduce((acc, val, idx) => {
if(val) acc.push(idx);
return acc;
}, []);
};
console.log(sieveUpto(24)); // [2, 3, 5, 7, 11, 13, 17, 19, 23]
에라토스테네스의 체는 2부터 시작해 각 소수의 배수들을 미리 제거해 나가는 방식으로, 대량의 소수를 구할 때 시간 복잡도 측면에서 큰 이점을 제공합니다. 상황에 맞게 두 방식 중 적절한 방법을 선택해 사용하시기 바랍니다.