[python] 파이썬 소수 구하기, 에라토스테네스의 체 - 시간 복잡도 최적화

소수 구하기 - 에라토스테네스의 체

1부터 N까지의 수 중에서 소수를 찾으려고 할 때 모든 수를 2부터 N-1까지의 수로 나누어 결과를 찾으면 시간 초과에 걸릴 가능성이 높습니다.

 

소수 여부를 알 수 있는 대표적인 에라토스테네스의 체 방법을 이용해 시간 초과를 피할 수 있습니다.

1. 2부터 N까지의 모든 자연수를 나열합니다. (1은 소수가 아님)
2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾습니다. (처음 i는 2)
3. 남은 수 중에서 i의 배수를 모두 제거합니다. (i의 배수이므로 소수가 아님 /  i는 제거하지 않음)
4. 더 이상 반복할 수 없을 때까지 2와 3번을 반복합니다.

n = 100
sosu = [True]*(n+1) # 초기에는 소수로 설정

# 에라토스테네스의 체 구현
for i in range(2, int(n**0.5)+1): # n의 제곱근까지의 수만 계산
  if sosu[i]:
    for j in range(2*i, n+1, i):
      sosu[j] = False

# 소수 출력
for i in range(2, n+1):
  if sosu[i]:
    print(i, end= ' ')

에라토스테네스의 체  성능 분석

에라토스테네스의 체 알고리즘의 시간 복잡도는 사실상 선형 시간에 가까울 정도로 매우 빠릅니다.

• 시간 복잡도는 O(NloglogN) 입니다.

• 에라토스테네스의 체 알고리즘은 다수의 소수를 찾아야 하는 문제에서 효과적으로 사용될 수 있습니다.