이 글에서는 아래 문제에 대한 해결 방법을 단계별로 살펴보겠습니다.
문제 정의
문제 — 하나의 숫자 n이 주어졌을 때, n보다 작거나 같은 모든 소수를 출력해야 합니다.
제약 조건 — n은 비교적 작은 수라고 가정합니다.
에라토스테네스의 체(Sieve of Eratosthenes)는 고대 그리스 수학자 에라토스테네스가 고안한 대표적인 소수 판별 알고리즘입니다. 2부터 n까지의 수 중에서 소수의 배수들을 차례로 걸러내면, 마지막에 남는 수들이 곧 소수가 됩니다. 일일이 나눗셈으로 검사하는 방식보다 훨씬 효율적이며, 시간 복잡도는 O(n log log n)입니다.
그럼 아래 구현 예시를 통해 해결 과정을 확인해 보겠습니다.
예제 코드
def SieveOfEratosthenes(n):
# True 값으로 초기화된 불리언 배열 생성
prime = [True for i in range(n + 1)]
p = 2
while (p * p <= n):
# 값이 그대로 유지되어 있다면 p는 소수
if (prime[p] == True):
# p의 모든 배수를 소수 후보에서 제거
for i in range(p * 2, n + 1, p):
prime[i] = False
p += 1
prime[0] = False
prime[1] = False
# 소수 출력
for p in range(n + 1):
if prime[p]:
print(p, end=" ")
# 메인 실행부
if __name__ == '__main__':
n = 33
print("33 이하의 소수는 다음과 같습니다:")
SieveOfEratosthenes(n)
출력 결과
33 이하의 소수는 다음과 같습니다: 2 3 5 7 11 13 17 19 23 29 31
동작 원리 설명
위 코드의 핵심 로직은 다음과 같습니다.
- 초기화 — 인덱스 0부터 n까지, 모든 수를 일단 소수 후보(True)로 표시한 불리언 배열을 만듭니다.
- 탐색 범위 — while 루프의 조건이
p * p <= n인 이유는, n 이하의 합성수는 반드시 √n 이하의 약수를 가지기 때문입니다. 따라서 √n까지만 검사하면 충분합니다. - 배수 제거 — p가 소수로 판명되면, p*2부터 시작해 p씩 증가하는 모든 배수를 False로 바꿔 소수 후보에서 제외합니다.
- 예외 처리 — 0과 1은 소수가 아니므로 명시적으로 False로 설정합니다.
- 출력 — 최종적으로 배열에서 True로 남아 있는 인덱스 값들이 곧 n 이하의 소수입니다.
모든 변수는 함수 내 지역 스코프(local scope)에 선언되며, 실행 흐름상 각 변수의 참조 관계는 위 설명과 같습니다.
결론
이 글에서는 파이썬으로 에라토스테네스의 체를 구현하여, 주어진 숫자 n 이하의 모든 소수를 효율적으로 찾는 방법을 알아보았습니다. 이 알고리즘은 소수를 대량으로 구해야 하는 상황에서 널리 활용되는 기본적이면서도 강력한 기법이므로, 꼭 익혀두시길 권장합니다.