에라토스테네스의 체, 소수 판별 알고리즘

소수 판별 알고리즘

1과 자기 자신으로만 나누어 떨어지는 숫자를 소수라고 한다.

X가 소수인지 판별하기 위해서 X를 2부터 X-1까지 나눠서 확인해야 한다.
하지만 이러면 시간복잡도는 $O(X)$이므로 X의 크기가 커지면 커질수록 효율적이지 못하다.

시간복잡도를 개선하기 위해서 2부터 X-1까지 확인하는 대신에 2부터 $\sqrt{x}$까지 확인한다.
예를 들어서 36의 약수는 다음과 같다.

• (1, 2, 3, 4, 6, 9, 12, 18, 36)

36의 약수 중에서 가운데 수 6을 기준으로 대칭적으로 곱을 통하여 36을 만들 수 있으므로, 결과적으로 $\sqrt{x}$까지만 확인하면 소수 판별이 가능하다.

이렇게 개선된 알고리즘의 시간복잡도는 $O(\sqrt{x})$이다.

import math

def prime_number(x):
  for i in range(2, int(math.sqrt(x)) + 1):
    if x % i == 0:
      return False
  return True

에라토스테네스의 체

개선된 소수 판별 알고리즘을 쓰더라도 여러 수에 대한 소수 판별에는 여전히 비효율적일 수 있다.
따라서 이러한 경우에는 에라토스테네스의 체라는 방법을 사용한다.

에라토스테네스의 체를 구하는 방법은 아래와 같다.

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.
2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수를 x를 찾는다.
3. i를 제외한 i의 배수를 모두 제거한다.
4. 더 이상 반복할 수 없을 때까지 2, 3번의 과정을 반복한다.

def prime_list(n):
  # 에라토스테네스의 체 초기화: n개 요소에 True 설정 (True이면 소수)
  sieve = [True] * n
  
  # n의 최대 약수가 sqrt(n) 이하이므로 i = sqrt(n) 까지 검사
  m = int(n ** 0.5)
  for i in range(2, m + 1):
    if sieve[i] == True:                # i가 소수이면
      for j in range(i + i, n, i):      # i이후 i의 배수들을 False 판정
        sieve[j] = False
  
  # 소수 목록 산출
  return [i for i in range(2, n) if sieve[i] == True]

• 결과:

prime_list(10)
# [2, 3, 5, 7]

prime_list(20)
# [2, 3, 5, 7, 11, 13, 17, 19]

max(prime_list(1000000)
# 999983

에라토스테네스의 체는 시간복잡도가 $O(Nlog(logN))$이기 때문에 선형 시간에 동작할 정도로 빠르다.
하지만 N의 크기 만큼 메모리를 저장하고 기억하므로 주의해야 한다.