에라토스테네스의 체(Sieve of Eratosthenes)

프로그래머스

문제 설명

1부터 n 사이에 있는 소수의 개수를 반환하는 함수를 작성해야 한다. 소수란 1과 자기 자신으로만 나누어지는 수를 의미하며, 1은 소수가 아니다.

처음 시도한 코드 (시간 초과)

function solution(n) {
    let answer = 0;
    for (let i = 2; i <= n; i++) {
        let flag = true;
        for (let j = 2; j <= Math.sqrt(i); j++) {
            if (i % j === 0) {
                flag = false;
                break;
            }
        }
        if (flag) {
            answer++;
        }
    }
    return answer;
}

이 코드는 O(n√n)의 시간 복잡도를 가집니다.

• i는 2부터 n까지 반복 (n번)
• j는 2부터 √i까지 반복 (√n번)

에라토스테네스의 체

에라토스테네스의 체 개념

• 2부터 n까지 모든 수를 소수라고 가정하고 배열을 만듭니다.
• 2부터 시작해서 해당 수의 배수를 모두 제거합니다. 
• 남아있는 수 중에서 가장 작은 소수를 찾아 그 배수를 제거합니다. 
• 이를 √n까지 반복하면 남아있는 수가 소수입니다.

function solution(n) {
    let primes = new Array(n + 1).fill(true);
    primes[0] = false;
    primes[1] = false; 

    for (let i = 2; i <= Math.sqrt(n); i++) {
        if (primes[i]) { // i가 소수라면
            for (let j = i * i; j <= n; j += i) {
                primes[j] = false; // i의 배수를 모두 제거
            }
        }
    }

    return primes.filter(v => v).length; // 남아있는 소수 개수 반환
}

에라토스테네스의 체 알고리즘의 시간 복잡도는 O(n * log(log n))의 시간 복잡도를 가집니다.

 

알고달레