1. 문제 설명
이번 문제는 주어진 수 N보다 작거나 같은 소수를 전부 구하는 것입니다. 소수란 1과 자기 자신만을 약수로 가지는 정수를 뜻합니다. 예를 들어, 2, 3, 5, 7, 11, 13 등은 소수입니다.
문제 정의
다음과 같은 조건을 만족하는 소수를 구하는 프로그램을 작성하세요.
함수 이름: find_primes
입력: 정수 N (2 ≤ N ≤ 10^6)
출력: N보다 작거나 같은 모든 소수를 리스트로 반환
2. 접근 방식
소수를 찾기 위해 가장 많이 사용되는 방법 중 하나는 ‘에라토스테네스의 체’라고 불리는 알고리즘입니다. 이 알고리즘은 주어진 범위 내의 모든 소수를 효율적으로 찾는 방법으로, 아래와 같은 단계로 진행됩니다.
- 2부터 N까지의 정수를 포함하는 리스트를 생성합니다.
- 리스트에서 2의 배수들을 모두 삭제합니다.
- 다음 남은 수에 대해 같은 과정을 반복합니다. (즉, 현재 수의 배수를 모두 삭제)
- N까지의 수를 모두 처리할 때까지 이를 반복합니다.
- 마지막까지 남은 수들이 소수입니다.
3. 알고리즘 구현
이제 위에서 설명한 에라토스테네스의 체 알고리즘을 파이썬으로 구현해 보겠습니다. 아래는 전체 코드입니다.
def find_primes(N):
# 0과 1은 소수가 아니므로 미리 배제합니다.
if N < 2:
return []
# 소수를 찾기 위한 리스트 초기화
sieve = [True] * (N + 1) # 모든 수를 소수 가능성으로 초기화
sieve[0], sieve[1] = False, False # 0과 1은 소수가 아님
for i in range(2, int(N**0.5) + 1): # 2부터 sqrt(N)까지 진행
if sieve[i]: # i가 소수일 경우
for j in range(i * i, N + 1, i): # i의 배수를 False로 설정
sieve[j] = False
# 소수 리스트 생성
primes = [i for i, is_prime in enumerate(sieve) if is_prime]
return primes
# 테스트
N = 100
print(find_primes(N)) # 출력: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
4. 코드 설명
코드는 다음과 같이 작동합니다:
- 우선, 리스트 ‘sieve’를 생성하여 N+1 크기의 배열을 True로 초기화합니다. 이 배열에서 인덱스는 수를 의미하고, 값이 True인 경우 해당 수가 소수임을 나타냅니다.
- 0과 1은 소수가 아니므로, 이 두 인덱스는 False로 설정합니다.
- 2부터 시작하여 sqrt(N)까지 반복문을 실행합니다. 이 과정에서 현재 수 i가 소수인지 확인합니다 (sieve[i]가 True). 만약 소수이면, i의 배수를 모두 False로 변경합니다.
- 모든 검사를 완료한 후, 최종적으로 True 값이 남아 있는 인덱스를 리스트로 만들어 소수를 반환합니다.
5. 성능 분석
에라토스테네스의 체 알고리즘은 O(n log log n) 복잡도를 가지며, 이는 매우 효율적인 편입니다. 따라서, 주어진 문제의 조건인 N ≤ 10^6에 대해서도 빠른 속도로 소수를 찾을 수 있습니다.
6. 결론
소수를 구하는 문제는 다양한 알고리즘을 사용할 수 있지만, 에라토스테네스의 체 알고리즘은 그 중에서 가장 효율적이고 직관적인 방법 중 하나입니다. 이 알고리즘을 활용하여 다양한 문제를 해결할 수 있으니, 꼭 익혀두시기 바랍니다!
7. 추가 참고 자료
더 깊이 있는 알고리즘을 공부하고 싶다면 아래의 자료를 추천합니다: