[수학] 에라토스테네스의 체(Sieve of Eratosthenes) 이론

💡 에라토스테네스의 체(Eratosthenes’ sieve) 개요

고대 그리스의 수학자 에라토스테네스가 고안한 소수 판별 알고리즘

자연수 $N^2$ 이하의 소수를 찾고 싶으면, $N$ 이하의 소수를 모두 찾아 그 소수들로 나누어 보면 된다.

🎯 목표

코딩 테스트에서 소수와 관련된 문제가 나오면 빠르게 소수를 찾기 위해 사용한다. 가장 간단하고 빠른 소수 판별 알고리즘이다.

🔑 알고리즘 동작 과정

1. 길이가 $N$인 배열을 생성하여 각 숫자가 소수인지 여부를 저장한다.
2. 2부터 $\sqrt N$ 이하의 자연수까지 숫자를 순회하며 소수인 경우 그 숫자의 배수를 모두 소수가 아니라고 표시한다.
3. 최종적으로 남아있는 수는 모두 소수이다.

🎨 시각적 설명

$N = 20$ 일 때, 소수를 찾는 과정은 다음과 같다. $N = 20$이므로 $\sqrt {20} = 4.4721…$이므로 4 이하의 자연수 숫자만 순회하면 된다.

1은 소수도 합성수도 아닌 자연수이므로 소수 판별에서 제외한다.

2는 소수이다. 2의 배수를 모두 삭제하면 아래와 같다.

3은 소수이다. 3의 배수를 모두 삭제하면 아래와 같다.

4는 소수가 아니다. 4의 배수는 삭제할 필요가 없다. 이미 2의 배수를 삭제하는 과정에서 4의 배수도 삭제되었기 때문이다.

앞서 말한대로 4 이하의 자연수로 삭제하는 과정을 끝냈다. 아래는 최종 소수 목록이다.

❓ 생각해보면 좋을 것들

왜 소수를 찾는 과정에서 제곱근을 사용하는가?

소수를 찾는 과정에서 제곱근을 사용하는 이유는 소수의 정의와 관련이 있다. 소수는 1과 자기 자신을 제외한 약수를 가지지 않는 수이다.

• 예를 들어, 20은 1, 2, 4, 5, 10, 20의 약수를 가진다.
• 위에 나열된 약수들은 양 끝 값을 서로 곱하면서 안으로 한 칸씩 이동하면 20이 되는 숫자들의 쌍이 된다.
  • 20의 약수 중 20을 만들어내는 숫자쌍은 1과 20, 2와 10, 4와 5이다.
• 숫자쌍으로 대응될 후반부 숫자들은 제곱근 이하의 숫자들로 대응되기 때문에 제곱근 이하의 숫자들만 순회하면 된다.

모든 소수 문제에 적용 가능한가?

굉장히 단순하고 좋은 알고리즘이지만 모든 소수 문제에 적용 가능한 것은 아니다.

• 에라토스테네스의 체는 특정 범위 내의 소수를 찾는 문제에 적용하면 좋은 알고리즘이고 특정 수에 대해 소수인지 아닌지 판별하는 알고리즘은 굉장히 효율적인 알고리즘이 많다.
• 효율성을 따지지 않는 문제라면 간단하게 시각적 설명에 나온 과정을 구현해내면 되기 때문에 에라토스테네스의 체를 사용하는 것이 좋다.

Mathematics Theory 카테고리 내 다른 글 보러가기