JavaScript에서 숫자 n을 인자로 받아, 가장 작은 소수부터 차례대로 n개의 소수를 담은 배열을 반환하는 함수를 작성해 보겠습니다.
소수란 무엇인가?
소수(素數)는 1과 자기 자신 외에는 어떤 수로도 나누어 떨어지지 않는 2 이상의 자연수입니다. 예를 들어 2, 3, 19, 37, 73 등이 대표적인 소수이며, 4나 6처럼 다른 약수를 함께 가지는 수는 합성수라고 부릅니다.
구현 아이디어
가장 직관적인 접근 방식은 문제를 두 단계로 나누는 것입니다.
- 소수 판별 함수 작성: 주어진 숫자가 소수인지 확인하는 isPrime 함수를 먼저 만듭니다.
- 반복문으로 소수 생성: 2부터 시작해 숫자를 하나씩 검사하며 소수일 때마다 배열에 추가하고, 배열의 길이가 n에 도달할 때까지 반복합니다.
1단계: 소수 판별 함수 isPrime
const isPrime = (n) => {
for(let i = 2; i <= n/2; i++){
if(n % i === 0){
return false;
}
};
return true;
};
isPrime 함수는 2부터 n/2까지의 정수로 n을 차례대로 나누어 봅니다. 중간에 한 번이라도 나누어 떨어지면 즉시 false를 반환하고, 끝까지 약수를 찾지 못했다면 true를 반환해 해당 숫자가 소수임을 알립니다.
2단계: n개의 소수를 생성하는 generatePrime 함수
const isPrime = (n) => {
for(let i = 2; i <= n/2; i++){
if(n % i === 0){
return false;
}
};
return true;
};
const generatePrime = num => {
const arr = [];
let i = 2;
while(arr.length < num){
if(isPrime(i)){
arr.push(i);
};
i = i === 2 ? i+1 : i+2;
};
return arr;
};
console.log(generatePrime(6));
console.log(generatePrime(16));
console.log(generatePrime(36));
코드 동작 설명
- arr: 생성된 소수를 저장할 빈 배열입니다.
- i = 2: 가장 작은 소수인 2부터 검사를 시작합니다.
- while(arr.length < num): 배열에 담긴 소수의 개수가 num에 도달할 때까지 반복합니다.
- i = i === 2 ? i+1 : i+2: 2를 검사한 이후에는 홀수만 검사합니다. 2를 제외한 모든 짝수는 합성수이므로 짝수를 건너뛰면 불필요한 연산이 줄어들어 성능이 향상됩니다.
실행 결과
위 코드를 실행하면 콘솔에 다음과 같이 출력됩니다.
[ 2, 3, 5, 7, 11, 13 ] [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53 ] [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151 ]
성능 최적화 팁
약수는 항상 쌍으로 존재하기 때문에, n이 약수를 가진다면 그중 하나는 반드시 √n 이하입니다. 따라서 isPrime의 반복 조건을 n/2 대신 Math.sqrt(n)까지만 검사하도록 바꾸면 판별 속도를 크게 개선할 수 있습니다.
const isPrime = (n) => {
if(n < 2) return false;
for(let i = 2; i <= Math.sqrt(n); i++){
if(n % i === 0){
return false;
}
}
return true;
};
이처럼 검사 범위를 √n으로 줄이면 큰 숫자를 다룰 때도 훨씬 빠르게 소수를 찾을 수 있습니다.