소수 찾기

소수 찾기는 간단하게 구현하면 쉽지만, 시간 복잡도를 줄이기 위해서는 에라토스테네스의 체를 사용해야한다. 소수를 찾는 문제는 간단하지만 라이브코딩으로 출제될 수 있으므로 알아두면 좋다.

에라토스테네스의 체

참고 : 위키백과

에라토스테네스의 체는 소수를 찾는데 사용된다.

알고리즘

• 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
• 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
  자기 자신을 제외한 2의 배수를 모두 지운다.
• 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
  자기 자신을 제외한 3의 배수를 모두 지운다.
• 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
  자기 자신을 제외한 5의 배수를 모두 지운다.
• 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
  자기 자신을 제외한 7의 배수를 모두 지운다.

위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.
그림의 경우, 11 ^ 2 > 120 이므로 11 보다 작은 수의 배수들만 지워도 충분하다. 즉, 120보다 작거나 같은 수 가운데 2, 3, 5, 7의 배수를 지우고 남는 수는 모두 소수이다.

소스 코드

const countPrimes = n => {
  const prime = Array(n).fill(true);
  prime[0] = prime[1] = false;

  for (let i = 2; i * i < n; i++) {
    if (prime[i]) {
      for (let j = i * i; j <= n; j += i) {
        prime[j] = false;
      }
    }
  }

  return prime.filter(num => num).length;
};
console.log(countPrimes(10));