자바스크립트 코딩테스트 강좌, 소수 구하기

안녕하세요! 오늘은 자바스크립트 코딩 테스트에서 자주 출제되는 ‘소수 구하기’ 문제에 대해 알아보겠습니다. 소수는 1과 자기 자신 외에 아무 정수로도 나눠 떨어지지 않는 자연수를 의미합니다. 예를 들어, 2, 3, 5, 7, 11은 모두 소수입니다. 이 글에서는 소수를 찾기 위한 알고리즘을 구현하고 그 과정을 자세히 설명드리겠습니다.

1. 문제 정의

주어진 정수 N이 있을 때, N 이하의 모든 소수를 출력하는 프로그램을 작성하시오.

입력: 정수 N (1 ≤ N ≤ 10,000)

출력: N 이하의 모든 소수를 한 줄에 출력

2. 알고리즘 선택

소수를 구하기 위해 사용될 대표적인 알고리즘은 에라토스테네스의 체(Sieve of Eratosthenes)입니다. 이 알고리즘은 매우 효율적이며, N 이하의 소수를 찾는 데 적합합니다. 알고리즘의 사용 이유는 다음과 같습니다:

O(N log log N)의 시간 복잡도로 매우 빠릅니다.
메모리 사용량이 적당하여 N이 10,000까지는 무난하게 처리할 수 있습니다.

2.1 에라토스테네스의 체 알고리즘 설명

에라토스테네스의 체 알고리즘은 다음과 같은 단계로 진행됩니다:

2부터 N까지의 모든 수를 리스트에 추가합니다.
리스트의 첫 번째 숫자인 2를 소수로 확정합니다. 2의 배수는 소수가 아니므로 리스트에서 제거합니다.
다음 수(3)를 소수로 확정하고, 3의 배수를 제거합니다. 이 과정을 반복합니다.
현재 수가 N의 제곱근보다 작거나 같은 경우에만 반복합니다.

3. 코드 작성

이제 위 알고리즘을 기반으로 자바스크립트로 코드를 작성해 보겠습니다.

function sieveOfEratosthenes(N) {
    const primes = [];
    const isPrime = new Array(N + 1).fill(true);
    isPrime[0] = isPrime[1] = false; // 0과 1은 소수가 아닙니다.

    for (let i = 2; i <= N; i++) {
        if (isPrime[i]) {
            primes.push(i); // i는 소수입니다.
            for (let j = i * 2; j <= N; j += i) {
                isPrime[j] = false; // i의 배수는 소수가 아닙니다.
            }
        }
    }
    return primes;
}

// 사용 예시
const N = 100; // N을 입력받습니다.
const primeNumbers = sieveOfEratosthenes(N);
console.log(primeNumbers.join(' ')); // 소수를 출력합니다.

4. 코드 분석

작성된 코드를 하나씩 살펴보겠습니다:

const isPrime = new Array(N + 1).fill(true);: N까지의 숫자 배열을 생성하고 모든 값을 true로 초기화합니다.
isPrime[0] = isPrime[1] = false;: 0과 1은 소수가 아니므로 false로 설정합니다.
for 루프를 통해 2부터 N까지의 수를 검사합니다. 만약 isPrime[i]가 true라면, 이는 i가 소수임을 의미합니다. 이 숫자를 primes 배열에 추가합니다.
또한, i의 모든 배수를 반복하여 false로 설정합니다.
이 과정을 통해 최종적으로 소수만 남은 배열을 반환합니다.

5. 테스트 케이스

이제 우리의 구현이 잘 작동하는지 확인하기 위해 몇 가지 테스트 케이스를 실행해 보겠습니다.

console.log(sieveOfEratosthenes(10)); // [2, 3, 5, 7]
console.log(sieveOfEratosthenes(50)); // [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
console.log(sieveOfEratosthenes(100)); // [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]

6. 결론

오늘은 자바스크립트에서 소수를 구하는 방법에 대해 알아보았습니다. 에라토스테네스의 체를 활용하여 효율적으로 소수를 찾아낼 수 있는 방법을 살펴보았고, 이를 바탕으로 실용적인 코드를 작성하였습니다. 이 코드를 통해 여러분의 알고리즘 실력을 한층 더 발전시키시길 바랍니다. 더불어, 코딩 테스트 준비에 많은 도움이 되기를 바랍니다!

7. 추가 학습 자료

더 많은 자료와 문제를 해결하고 싶다면 다음의 리소스를 참고하세요:

LeetCode – 다양한 알고리즘 문제와 해설
HackerRank – 코딩 테스트 문제 풀이 및 연습
Codewars – 다양한 언어로 문제를 해결하며 코딩 연습