에라토스테네스의 체

고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법

 

체로 거르듯 수를 걸러낸다고 하여 에라토스테네스의 체 라고 불린다.

 

시간복잡도: O(n log log n)

---

소수를 빠르게 찾는 방법으로, 전체 범위를 확인하며, 배수를 빠르게 걸러준다.

 

if 문을 통해 for문을 전범위 확인 할 필요가 없어지므로 큰 시간복잡도의 시간이 n**2에서 n log log n 으로 줄어든다.

 

아래는 파이썬 코드로 확인해볼 수 있는 예시 문제

 

N = int(input())
prime = []
check = [0] * (N + 1)

for i in range(2, N + 1):
    if not check[i]:
        prime.append(i)
    for j in range(i + i, N + 1, i):
        check[j] = 1

print(*prime)

N까지 의 숫자중 소수만을 출력하는 문제로, 두번째 for문을 보면 알 수 있듯, 해당 수의 배수들을 전부 check 처리 시켜, 코드의 속도를 줄여준다.