[Level 1] 소수 찾기

문제 설명

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

제한 조건

• n은 2 이상, 1,000,000 이하의 자연수입니다.

문제 풀이

이 문제는 '에라토스테네스의 체'의 원리를 적용해 해결하면 됩니다. 에라토스테네스의 체는 모든 자연수가 담긴 테이블이며, 처음에는 모든 자연수를 소수라 가정합니다. 테이블을 만든 후에는 소수 검증을 위해 숫자 2부터 순회를 시작하는데, 2는 소수지만 2의 배수는 모두 소수가 아니다라는 정보를 바탕으로 테이블을 갱신합니다. 숫자 2에 대한 처리가 끝나면, 3에 대해서도 처리하면 됩니다. 그리고 4의 차례가 되었을 때는 이미 2의 배수는 소수가 아니다라고 판명났기 때문에 건너뜁니다.

이 원리를 코드에 적용시켜 해결한 코드입니다.

const solution = (n) => {
  // 소수 테이블을 만드는데, 일단은 1부터 n까지 모두 소수라 가정
  const primes = Array.from({ length: n + 1 }, () => true);
  // 0과 1은 소수가 아니니 false로 변경
  primes[0] = primes[1] = false;

  // 소수를 구할 때 사용하는 에라토스테네스의 체를 구현
  // 2는 소수지만, 2의 배수는 소수가 아니다.
  for (let i = 2; i <= Math.sqrt(n); i++) {
    if (!primes[i]) continue;
    for (let j = i * 2; j <= n; j += i) {
      primes[j] = false;
    }
  }

  // true인 값들의 개수를 구해 반환
  return primes.filter((v) => v).length;
};

const inputs = [10, 5];
inputs.forEach((input) => console.log(solution(input)));

Array.from의 첫 번째 인자로 length를 담은 객체를 지정하게 되면, 명시한 크기의 배열을 만들어 줍니다. 크기를 n+1로 한 이유는 배열을 참조할 때 직관적으로 참조하기 위함입니다. (배열의 인덱스는 0부터 시작하지만, 숫자 1을 인덱스 1로 참조하고 싶기 때문!) 그리고 숫자 0과 1은 소수가 아니므로 에라토스테네스의 체를 구현하기 전에 미리 처리했습니다.

마지막으로 보통 소수를 검증할 때는 굳이 마지막까지 확인할 필요 없이, 제곱근까지만 확인해도 됩니다.