소수 찾기

나의 풀이

n이 소수인지 아닌지에 관한 알고리즘 문제는 전에 풀어본 적이 있어 이 문제도 비슷하게 풀리지 않을까 했었는데, 소수 판별과 1부터 n까지의 수 중 소수인 것을 골라내는 것은 두 문제의 핵심이 다르기 때문에 쉽사리 코드를 작성할 수 없었다.

어떻게 풀지 몇 분은 고민했는데 아무리 코드를 작성해도 원하는 답을 반환하지 못하여 다른 방법이 있을까 구글링하던 차에 에라토네스의 체라는 소수를 찾는 방법을 알게 되었다.

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

이후 8의 배수는 지울 필요가 없다. 2의 배수에서 이미 지워지기 때문이다. 9의 배수 또한 3의 배수에서 이미 지워졌고, 10의 배수 또한 2의 배수에서 이미 지워졌다.

이런 방법으로 n이하의 소수를 찾을 떄에는 1부터 n까지 나열한 다음 2의 배수, 3의 배수, 5의 배수, ... n의 제곱근의 배수까지를 제외하면 된다. 만약 n보다 작은 어떤 수 m이 m = ab라면 a와 b중 적어도 하나는 n의 제곱근 이하의 수이다.

즉, n보다 작은 합성수 m은 n의 제곱근보다 작은 수의 배수만 체크해도 전부 지워지기 때문에 1부터 n까지의 소수를 찾는 경우에는 2부터 n의 제곱근까지의 배수를 지워주면 된다.

이 개념을 이용해서 내가 제출한 코드는 아래와 같다.

function solution(n) {
  // 0부터 n까지 true가 담긴 배열 만들기
  // 인덱스와 숫자가 같게 하기 위해 0부터 담음
  // 0과 1은 어차피 소수가 아니기 때문에 false 담아놓음
  const arr = Array(n + 1)
    .fill(true)
    .fill(false, 0, 2);
  
  // n의 제곱근까지 순회하면서
  for (let i = 2; i * i <= n; i++) {
    if (arr[i]) {
      // 2부터 n의 제곱근의 배수는 소수가 아님 -> false로 바꾸기
      for (let j = i * i; j <= n; j += i) {
        arr[j] = false;
      }
    }
  }
  // true인 것(소수)의 개수 구하기
  return arr.filter((e) => e).length;
}

손코딩

n이 25인 경우를 가정하여 직접 손코딩을 해보았다.