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

에라토스테네스의 체란?

2부터 주어진 숫자까지의 소수들을 찾는 방법으로 고대 그리스 수학자 에라토스테네스가 발견하였다.

원리는 2부터 주어진 숫자까지 모든 구간의 수를 나열한 후

2부터 시작해 발견되는 소수의 배수를 지워나가는 방식으로 소수를 찾는다.

 

자세한 방법은 위키백과에 나와있다. - [링크]

코드

1. 자신을 포함 안시키는 경우

def prime_list(n):
  # 에라토스테네스의 체 초기화: n개 요소에 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]

101에 대해 출력 시 아래와 같이 나오는데

print(prime_list(101))
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

101도 포함시키고 싶다면 m을 구할 때를 제외하고 각각의 n이 사용되는 곳에 +1을 해주면 된다.

 

2. 자신을 포함시키는 경우

def prime_list(n):
  # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
  sieve = [True] * (n + 1)

  # 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+1, i): # i이후 i의 배수들을 False 판정
        sieve[j] = False

  # 소수 목록 산출
  return [i for i in range(2, n+1) if sieve[i] == True]

 

+ 대상이 소수인지 체크

위에서 살펴본 에라토스테네스의 체는 주어진 숫자까지의 소수들을 찾는 방법이었는데

주어진 숫자가 소수인지를 체크하는 방법이 더 궁금하다면 아래와 같이 확인할 수 있다.

코드

def check_decimal(n):
  # n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사
  m = int(n ** 0.5)
  for i in range(2, m+1):
    if n % i == 0:
      return False
  return True

마찬가지로 n의 최대 약수가 sqrt(n) 즉, n의 제곱근 이하이므로

i에 대해  제곱근 이하까지 검사하는 방법을 통해 

그냥 2부터 n까지 다 비교하는것보다 훨씬 자원을 절약할 수 있다.

* 101에 대해 체크할 때 2부터 100까지 모두 체크하는 방법보다 2부터 10까지만 체크하면 된다는 얘기

 

소수인지 확인하는건 다른 알고리즘과 더불어 같이 사용되야 하는 상황이 자주 나오니

그냥 외우자!