소수 찾기

소수 찾기

2020.07.27

const isPrimeNumber = (num) => {
  // 1이하는 소수 아님
  if (num <= 1) {
    return false;
  }

  // 2와 3은 소수임
  if (num <= 3) {
    return true;
  }

  // 2와 3은 소수지만 2와 3의 배수는 소수가 아님
  // 아래의 반복문에서 2와 3의 배수는 체크하지 않기 위해 필요하다.
  if (num % 2 == 0 || num % 3 == 0) {
    return false;
  }

  // 4는 위에서 걸렸으니 5부터 시작
  for (let i = 5; i * i <= num; i += 6) {
    // 5가 6k-1의 형태이니
    // 전자는 6k-1을, 후자는 6k+1의 배수를 걸러내기 위함
    if (num % i == 0 || num % (i + 2) == 0) {
      return false;
    }
  }

  // 에라토스테네스의 체는 결국 n이라는 숫자가 있을 때
  // n의 제곱근보다 작거나 같은 소수들로 n이 나누어 떨어지지 않는다면 소수로 판단할 수 있다는 공식이다.
  // 2와 3, 그리고 6k-1, 6k+1로 n이 나누어 떨어지지 않는다면 소수이므로
  return true;
};

const solution = (n) => {
  let count = 0;
  for (let i = 2; i <= n; i++) {
    if (isPrimeNumber(i)) {
      count++;
    }
  }
  return count;
};

• 워낙 유명한 문제인데다 자료구조 책에서도 본 적이 있어 사실 기억에 의존해서 풀었다.

• 에라토스테네스의 체

  • n이라는 숫자가 있을 때 1부터 n까지 나열한 뒤 n의 제곱근보다 작거나 같은 소수들의 배수를 지우면 소수만이 남는다.

  • 여기서 n의 제곱근보다 작거나 같은 소수는 2와 3을 제외하고는 모두 6K-1 또는 6K+1의 형태를 지닌다

  • 즉, n의 제곱근보다 작거나 같은 소수(2와 3 그리고 6k-1, 6k+1)로 n이 나누어 떨어지지 않으면 n은 소수라는 것이다.