[알고리즘] 소수를 효율적으로 구하자 : 에라토스테네스의 체

서론

• 소개: 에라토스테네스의 체는 고대 그리스 수학자 에라토스테네스가 제안한 소수를 찾는 효율적인 알고리즘입니다. 이 포스팅에서는 에라토스테네스의 체 알고리즘의 원리와 구현 방법을 설명합니다.
• 중요성: 소수는 암호학, 수론 등 여러 분야에서 중요한 역할을 합니다. 에라토스테네스의 체는 큰 범위에서 소수를 빠르게 찾을 수 있는 강력한 도구입니다. 뒤에서 백준 문제중 시간초과로 풀리지 않는 문제를 해결할 수 있습니다.

본론

1. 간략 설명
   • 정말 말 그대로 체를 생각하시면 됩니다. 전체의 숫제를 소수로 보고 어떤 숫자(2, 3, ... 앞에서 부터 시작하는 소수들)의 배수를 제외한다면 소수만 남게 되는 것이 이 개념의 포인트입니다.

     

     2의 배수를 거르고... 3의 배수를 거르고...

2. 에라토스테네스의 체란?
   • 정의: 에라토스테네스의 체는 주어진 범위 내에서 소수를 찾기 위한 효율적인 알고리즘입니다.
   • 원리: 2부터 시작하여 각 숫자의 배수를 제거하는 방식으로 소수를 찾습니다.
3. 알고리즘의 작동 원리
   • 단계별 설명:
     1. 2부터 n까지의 모든 정수를 나열합니다.
     2. 각 소수의 배수들을 소수가 아니라고 표시합니다.
     3. 더 이상 제거할 수 없는 숫자가 남지 않을 때까지 이 과정을 반복합니다.
   • 예제:
     • 예를 들어, 30까지의 소수를 찾는 과정을 시각화합니다.
4. 에라토스테네스의 체 구현 (파이썬)
   • 코드:

     import math
     
     def sieve_of_eratosthenes(n):
         is_prime = [True] * (n + 1)
         is_prime[0] = is_prime[1] = False # 0과 1은 소수가 아님
     
         for i in range(2, int(math.sqrt(n)) + 1):
             if is_prime[i]:
                 for j in range(i * i, n + 1, i):
                     is_prime[j] = False
     
         return [i for i in range(2, n + 1) if is_prime[i]]

   • 설명:
     • is_prime 배열을 생성하고 초기화합니다.
     • 2부터 √n까지 반복하여 각 소수의 배수를 False로 설정합니다.
     • 소수 목록을 반환합니다.
5. 응용 예제
   • 백준 문제 1929: 소수 구하기:
     • 주어진 두 수 M과 N 사이의 모든 소수를 찾는 문제를 에라토스테네스의 체로 해결합니다.
   • 백준 문제 6588: 골드바흐의 추측:
     • 주어진 짝수를 두 소수의 합으로 표현하는 문제를 에라토스테네스의 체로 해결합니다.

결론

• 요약: 에라토스테네스의 체는 간단하면서도 매우 효율적인 소수 찾기 알고리즘입니다. 이를 통해 소수를 빠르게 찾고, 다양한 문제를 해결할 수 있습니다.
• 응용 가능성: 소수는 다양한 분야에서 중요한 역할을 합니다. 에라토스테네스의 체를 이해하고 구현하면, 수학적 문제뿐만 아니라 암호학 등의 실용적인 문제도 해결할 수 있습니다.
• 추가 자료: 더 깊이 있는 학습을 위해 관련 자료나 참고 문헌을 소개합니다.

참고 자료

• Wikipedia: Sieve of Eratosthenes