[LeetCode] 204. Count Primes

Count the number of prime numbers less than a non-negative number, n.

 

Example:

Input: 10 Output: 4 Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

 

해당 문제를 풀 때, 처음에는 단순하게 접근하여 이중 for문으로 구현하려고 하였으나 Time Limit Exceeded 제약에 걸려버려 통과를 할 수 없는 상황이 발생했습니다. 해당 문제를 고민하다가 분명 시간복잡도를 줄이기 위한 좋은 아이디어가 존재할거라 생각하여 리서치한 결과 에라토스테네스의 체라는 소수 판별 방법이 존재하는 것을 알게 되었습니다. 접근 방법은 아래와 같습니다.

 

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
2. 2는 소수이므로 오른쪽에 2를 쓴다.
3. 자기 자신을 제외한 2의 배수를 모두 지운다.
4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다.
5. 자기 자신을 제외한 3의 배수를 모두 지운다.
6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다.
7. 자기 자신을 제외한 5의 배수를 모두 지운다.
8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다.
9. 자기 자신을 제외한 7의 배수를 모두 지운다.
10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

쉽게 말해서 2, 3, 5, 7의 배수를 모두 지우고 남은 값들은 모두 소수라는 접근 방법입니다. (2, 3, 5, 7은 값에 포함)

 

구현

const countPrimes = (n) => {	
	// less than n
	if (n <= 2) {
  	return 0;
  }
	
  let primeArray = [];
  // n - 1의 길이만큼의 배열의 요소들을 모두 소수라고 가정하고 true로 초기값 설정
  for (let i = 2; i < n; i++) {
  	primeArray.push(true);
  }
  
  for (let i = 2; i < n; i++) {
  	let index = i - 2;
    // 해당 인덱스의 값이 true면 해당 배수의 인덱스의 값을 false로 바꾼다.
    if (primeArray[index]) {
    	while(true) {
        if (index > n) {
        	break;
        }
        
      	index += i;
        if (typeof primeArray[index] !== 'undefined') {
        	primeArray[index] = false;
        }      	
      }
    }
  }
  
  // 요소가 true일 경우 count++
  return primeArray.reduce((acc, curr) => {
  	if (curr) {
    	return acc + 1;
    }
    return acc;
  }, 0)
}

console.log(countPrimes(2)); // 0
console.log(countPrimes(10)); // 4

primeArray[index]의 배수들을 모두 false로 바꿈으로써 검증해야되는 요소들의 수가 줄어들어 기존의 이중 for문으로 구현한 로직보다 훨씬 효율적으로 알고리즘을 수행하는 것을 확인할 수 있었습니다.