[알고리즘] Count Primes(소수찾기)

문제설명

leetcode와 프로그래머스에 있는 소수찾기를 진행했다.

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

프로그래머스
1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.

제한사항

• leetcode : 0 <= n <= 5 * 106
• 프로그래머스 : n은 2이상 1000000이하의 자연수입니다.

알고리즘

1. 0,1은 소수가 아니므로 제외한다
2. isPrime 함수를 만들어서 소수인지 아닌지 판별한다.
   2-1. 나누어떨어지는 값은 소수가 아니므로 false , 나누어떨지지 않으면 소수이므로 true
3. 만약 isPrime 함수에 들어간 i 가 소수라면(true) 카운터를 올려준다.
4. 2~3단계를 반복한다.

var countPrimes = function(n) {
   if(n < 2) return false;
   let count = 0;

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

위 코드를 통해 정확성면에서는 올라갔지만, 효율성에서는 떨어지는 코드로 판별되었다.

이를 보완하기 위해 에라토스테네스의 체를 이용하게 된다.

에라토스테네스의 체
1 ~ n까지의 수에서 n의 소수는 n의 제곱근까지의 배수(2,3,5,7)를 모두 제외하면 n까지의 소수만 남게되는 알고리즘 : 위키

소수판별에 대해 코드스테이츠 초반에 풀었던 문제로 기억하는데, 당시 에라토스테네스의 체 이해 부분은 버거웠었다.

다른 사람의 코드 풀이 및 자체적으로 이해를 시도했고, 그 결과 코딩 인터뷰에서 원활하게 설명을 진행할 수 있었다.

다만 for문 설명은 아직 부족한 부분이 있으니 좀더 보완해야겠다.

function solution(n){
    // 2~n까지 소수 설정 → 0부터 시작이므로 배열의 크기 1개를 늘려준다.
    let hashArr = new Array(n+1).fill(true);
    // 0번째,1번째 소수에서 제외
    hashArr[0] = false;
    hashArr[1] = false;
    // 2부터 ~ i*i<= n 각각의 배수를 지워간다.
    for(let i=2; (i*i) <= n; i++){
        // 제곱근까지의 배수만 제외하고
        if(hashArr[i]){ // 다음i의 값이 처리가 되었다면, 아래 for문을 실행
            //i*i 미만은 처리되었으므로 j의 시작값이 i*i로 최적화
            for(let j=i*i; j <= n; j += i){ // 소수는 true, j += i를 통해 배수 제외
              //2*(2+1), 2*(2+2)
             hashArr[j] = false;     
            }
        }
    }

   return hashArr.filter((isPrime)=>isPrim).length;
}

참조1
참조2
참조3