LeetCode - 204. Count Primes

문제

설명

자연수 중에서 n까지 소수의 개수를 반환하는 문제다.

전제 조건에 n의 값이 최대 $5 * 10^6$ 이므로 수 하나하나 약수가 있는지 나눠가면서 판별하면 Time Complexity가 O(N^2)으로 매우 높아지기에 에라토스테네스의 체라는 알고리즘을 사용해 문제를 해결하기로 했다.

에라토스테네스의 체

1. 에라토스테네스의 체는 가장 먼저 소수를 판별할 범위만큼 배열을 할당하여, 해당하는 값을 넣어주고, 이후에 하나씩 지워나가는 방법을 이용한다.

2. 배열을 생성하여 초기화한다.

3. 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다.(지울 때 자기자신은 지우지 않고, 이미 지워진 수는 건너뛴다.)

4. 2부터 시작하여 남아있는 수를 모두 출력한다.

풀이

/**
 * @param {number} n
 * @return {number}
 */
var countPrimes = function(n) {
    // 2부터 n까지 숫자를 담을 배열
  	let nums = [];
    let cnt = 0;
  	
  	// 배열에 2번 인덱스부터 n번 인덱스까지 초기값을 1로 설정(1이면 소수)
    for(let i = 2; i <= n; i++){
        nums[i] = 1;
    }
    
   	/* 
     * n의 제곱근까지만 판별하는 이유는 어떤 수의 소수의 여부를 확인 할 때는, 
     * 특정한 숫자의 제곱근 까지만 약수의 여부를 검증하면 O(N^1/2)의 시간 복잡도로 
     * 빠르게 구할 수 있다.
     */
    for(let i = 2; i < Math.sqrt(n); i++){
      	// 자기 자신을 제외한 배수를 소수에서 제외한다.
        for(let j = i*i; j < n; j += i){
            nums[j] = 0;
        }
    }
    
  	// 소수로 남은 숫자의 개수를 센다
    for(let i = 2; i < n; i++){
        if(nums[i] === 1) ++cnt;
    }
    
    return cnt;
};

Reference

• [Algorithm] 에라토스테네스의 체 - Junseo Kim
• 에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전