소수 판별법

1. 기본적인 소수 판별법 (Trial Division)

• 시간 복잡도: O(√N)
• 하나의 수 N에 대해 2부터 √N까지 나누어보는 방식
• 간단하지만 큰 수에 대해서는 비효율적

function isPrime(n) {
    if(n < 2) return false;
    for(let i = 2; i <= Math.sqrt(n); i++) {
        if(n % i === 0) return false;
    }
    return true;
}

2. 에라토스테네스의 체

• 시간 복잡도: O(N log log N)
• 공간 복잡도: O(N)
• 범위 내 모든 소수를 한번에 찾을 때 효율적
• 메모리를 많이 사용하는 단점

function sieve(max) {
    let isPrime = new Array(max + 1).fill(true);
    isPrime[0] = isPrime[1] = false;

    for(let i = 2; i * i <= max; i++) {
        if(isPrime[i]) {
            for(let j = i * i; j <= max; j += i) {
                isPrime[j] = false;
            }
        }
    }
    return isPrime;
}

3. 밀러-라빈 소수 판별법

• 시간 복잡도: O(k log³ n)
  • k는 테스트 횟수(witness 수)
  • 실제로는 매우 빠름
• 확률적 알고리즘이지만 작은 수의 witness로도 매우 정확
• 매우 큰 수의 판별에 적합

선택 가이드:

1. N이 작은 경우 (~10^6): 기본 소수 판별법
2. 범위 내 모든 소수가 필요한 경우: 에라토스테네스의 체
3. 매우 큰 수의 판별이 필요한 경우: 밀러-라빈

실제 사용 예:

// N이 백만 이하인 경우
if (N <= 1000000) {
    return isPrime(N);  // 기본 소수 판별법
}
// 범위 내 모든 소수가 필요한 경우
else if (needAllPrimes && N <= 10000000) {
    return sieve(N);    // 에라토스테네스의 체
}
// 매우 큰 수의 경우
else {
    return millerRabin(N);  // 밀러-라빈
}

---

에라토스테네스의 체를 사용하여 소수를 구하는 자바스크립트 코드

1. 기본적인 방식:

function sieveOfEratosthenes(n) {
    // 배열 초기화
    let prime = new Array(n + 1).fill(true);
    prime[0] = prime[1] = false;

    // 에라토스테네스의 체 알고리즘
    for (let i = 2; i * i <= n; i++) {
        if (prime[i]) {
            for (let j = i * i; j <= n; j += i) {
                prime[j] = false;
            }
        }
    }

    // 소수 배열 만들기
    let primes = [];
    for (let i = 2; i <= n; i++) {
        if (prime[i]) {
            primes.push(i);
        }
    }

    return primes;
}

console.log(sieveOfEratosthenes(30));
// 출력: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

2. 최적화된 방식:

function sieveOfEratosthenes(n) {
    // 홀수만 체크하는 최적화된 버전
    let prime = new Array(Math.floor(n/2)).fill(true);
    let primes = [2];  // 2는 유일한 짝수 소수

    for (let i = 3; i <= n; i += 2) {
        if (prime[Math.floor(i/2)]) {
            for (let j = i * i; j <= n; j += 2*i) {
                prime[Math.floor(j/2)] = false;
            }
        }
    }

    // 결과 수집
    for (let i = 3; i <= n; i += 2) {
        if (prime[Math.floor(i/2)]) {
            primes.push(i);
        }
    }

    return primes;
}

console.log(sieveOfEratosthenes(30));
// 출력: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

3. Set을 사용한 방식:

function sieveOfEratosthenes(n) {
    let numbers = new Set();

    // 2부터 n까지의 숫자를 Set에 추가
    for(let i = 2; i <= n; i++) {
        numbers.add(i);
    }

    // 에라토스테네스의 체 적용
    for(let i = 2; i * i <= n; i++) {
        if(numbers.has(i)) {
            for(let j = i * i; j <= n; j += i) {
                numbers.delete(j);
            }
        }
    }

    return Array.from(numbers);
}

console.log(sieveOfEratosthenes(30));
// 출력: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

각 방식의 특징:

1. 기본적인 방식:
   • 이해하기 쉽고 직관적
   • 메모리를 다소 많이 사용
2. 최적화된 방식:
   • 짝수를 제외하고 홀수만 체크하여 메모리와 시간을 절약
   • 코드가 약간 복잡
3. Set을 사용한 방식:
   • 코드가 간결하고 이해하기 쉬움
   • Set 객체를 사용하여 메모리 사용량이 다소 높을 수 있음

실제 사용 시에는 필요한 범위와 성능 요구사항에 따라 적절한 방식을 선택하면 됩니다.