에라토스테네스의 체는 소수를 찾아내기 위한 알고리즘으로, 교과 과정에서도 배우는 내용 중 하나다. 이 알고리즘은 LeetCode 204. Count Primes 와 같은 인터뷰에도 종종 등장하므로 알고 있으면 매우 유용하다.
고대 그리스 수학자 에라토스테네스가 발견한 이 알고리즘은 '체'로 치듯이 수를 걸러낸다고 해 '에라토스테네스의 체'로 불린다. 이 알고리즘의 포인트는 배수와 제곱근을 활용하는 것이다. 예를 통해 이해해보자.
- 1부터 100까지의 숫자 중 소수를 찾는다 가정하자.
- 1부터 100까지의 숫자를 나열해보자.
- 작은 숫자부터 시작을 하고, 특수한 경우인 1을 우선 지운다.
- 2를 제외한 2의 배수를 지운다. (배수 활용 시작)
- 3을 제외한 3의 배수를 지운다.
- 4의 배수는 이미 2의 배수를 통해 지웠으므로, 다음 숫자로 넘어가자.
- 5를 제외한 5의 배수를 지우고, 6의 배수는 2와 3을 통해 지워졌으므로 7로 넘어가자.
- 같은 방식으로 10까지만 확인하면, 11부터는 확인이 불필요하다. 11의 배수는 이미 11에 2부터 9까지 곱한 경우 (22, 33, ..., 99) 에 대해 지워졌기 때문이다. (제곱근 활용)
아래는 이에 대한 Python 구현이다. 참고로 시간 복잡도는 O (n log log n) 이다.
import math
class Solution:
def countPrimes(self, n: int) -> int:
if n <= 1:
return 0
isPrime = [1] * n
isPrime[0], isPrime[1] = 0, 0
for i in range(int(math.sqrt(n)) + 1):
if isPrime[i]:
cur = i * 2
while cur < n:
isPrime[cur] = 0
cur += i
return sum(isPrime)
참고
'기술(Tech, IT) > 알고리즘(Algorithm)' 카테고리의 다른 글
[Algorithm] Rabin-Karp Algorithm (라빈-카프 알고르짐) (1) | 2024.04.04 |
---|---|
[Algorithm] Lowest Common Ancestor (LCA) (0) | 2024.03.30 |
[Tech, Algo] Adaptive Beamforming (적응형 빔형성) (0) | 2024.03.03 |
[Algorithm] Checksum (체크섬) (1) | 2024.02.16 |
[Algorithm] Stack vs Heap (스택 vs 힙) (0) | 2023.10.25 |