🎨 에라토스테네스의 체 (소수찾기 알고리즘)

🎨 소수찾기

• 소수란 1과 자기 자신만을 약수로 가지는 수로 일반적으로 아래 코드와 같이 소수를 찾을 수 있다.

  const isPrimeNumber = (n) => {
    for (let i = 2; i < n; i++) {
      if (n % i === 0) return false;
    }
    return true;
  };
  

• 위의 방법을 적용한다면 소수 판별 알고리즘의 시간복잡도는 O(n)이 된다. 2부터 N까지 반복하면서 나누어 떨어지는지 아닌지 확인해야 하기 때문이다.

🎨 개선된 소수찾기

• 약수의 특징을 활용하여 소수를 더 효율적인 방법으로 찾을 수 있다.

• 만약 n이 소수가 아니라면 약수를 가질텐데 이때 약수는 n = a * b (a와 b는 n의 약수)로 표현할 수 있다. 이때 a 나 b 둘중 하나는 무조건 제곱근보다 작은 수여야 한다.

• 즉 n이 소수가 아니라면 √n까지 약수가 반드시 하나 이상 있어야 한다는 것이기 때문에 소수의 판별은 제곱근까지만 하면 된다.

  const isPrimeNumber = (n) => {
    for (let i = 2; i <= Math.sqrt(n); i++) {
      if (n % i === 0) return false;
    }
    return true;
  };

• 위의 방법을 적용한다면 소수 판별 알고리즘의 시간복잡도는 O(√n)이 된다.

🎨 에라토스테네스의 체

• 만약 1부터 1,000,000까지의 모든 소수를 판별해야 하는 경우 위 방법을 사용하여 소수를 판별하는 것은 제곱근까지 검사하는 개선된 방법을 적용해도 느릴 수 있다.
• 따라서 여러 개의 수를 소수판별 하는 경우에는 에라토스테네스의 체라는 방법을 사용한다.
• 고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법으로 이 방법은 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체' 라고 부른다.

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.
2. 회색으로 색칠된 수는 소수인지 아닌지 판별하지 않은 수이다. 회색 수 중 가장 작은 2부터 판별을 시작한다.
3. 자기 자신을 제외한 2의 배수를 모두 지운다. (연한 빨간색)
4. 남은 회색 수 중 가장 작은 수는 3이므로 자기 자신을 제외한 3의 배수를 모두 지운다. (연한 초록색)
5. 남은 회색 수 중 가장 작은 수는 5이므로 자기 자신을 제외한 3의 배수를 모두 지운다. (연한 파란색)
6. 남은 회색 수 중 가장 작은 수는 7이므로 자기 자신을 제외한 3의 배수를 모두 지운다. (연한 노란색)
7. 구하고자 하는 구간의 제곱근까지 해당 로직을 반복해준다.
   위 예시에서는 구하고자 하는 구간(n)의 크기가 120이기 때문에 n의 제곱근인 11까지만 위의 과정을 반복해줘도 충분하다.

🎨 소스코드(JS)

const n = 120;
const primeNumber = Array.from({ length: n + 1 }).fill(true);

for (let i = 2; i <= Math.sqrt(n); i++) {
  // i가 소수인 경우
  if (primeNumber[i]) {
    for (let j = i * 2; j <= n; j = j + i) {
      primeNumber[j] = false;
    }
  }
}


for (let i = 2; i <= n; i++) {
  if (primeNumber[i]) console.log(i);
}

🎨 Ref

• 이것이 코딩테스트다
• https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4#cite_note-1