정의

에라토스테네스 체는 고대 그리스 수학자 에라토스테네스가 발명한 소수 찾기 알고리즘입니다. 체로 모래를 거르듯이, 배수를 하나씩 지워나가면 소수만 남습니다.

핵심 특성

• ✓2부터 시작해서 아직 지워지지 않은 숫자가 다음 소수
• ✓각 소수의 배수를 모두 지워나감
• ✓√N까지만 검사하면 충분 (최적화)
• ✓O(n log log n) 시간복잡도로 매우 빠름

시간 복잡도