[알고리즘] 이것이 취업을 위한 코딩 테스트다 with 파이썬 - 에라토스테네스의 체

[알고리즘] 이것이 취업을 위한 코딩 테스트다 with 파이썬 - 에라토스테네스의 체

• 에라토스테네스의 체: 여러 개의 수가 소수인지 아닌지를 판별할 때 사용하는 대표 알고리즘. N 보다 작거나 같은 모든 소수를 찾을 때 사용할 수 있다.
• 알고리즘은 다음과 같다.
  1. 2부터 N까지의 모든 자연수를 나열한다.
  2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다.
  3. 남은 수 중에서 i의 배수를 모두 제거한다.(i는 제거하지 않는다)
  4. 더 이상 반복할 수 없을 때까지 2번과 3번을 반복한다.

---

• 소스코드 예제 - N = 1000 으로 설정

  # 시간복잡도: O(NloglogN)
  import math
  
  n = 1000
  arr = [True for i in range(n+1)] # 처음엔 모든 수가 소수(True)인 것으로 초기화(0과 1은 제외)
  
  for i in range(2, int(math.sqrt(n)) + 1): # 2부터 n의 제곱근까지의 모든 수를 확인하며
      if arr[i] == True: # i가 소수인 경우(남은 수인 경우)
          # i를 제외한 i의 배수 모두 지우기
          j = 2
          while i * j <= n:
              arr[i * j] = False
              j += 1
  
  # 모든 소수 출력
  for i in range(2, n+1):
      if arr[i]:
          print(i, end = " ")

  이 알고리즘은 메모리를 많이 잡아먹는다. 따라서 에라토스테네스의 체를 이용해야 하는 경우 N이 1,000,000 이내로 주어지는 경우가 많다. 그렇게 하면 이론상 400만 번 정도의 연산으로 문제를 해결할 수 있으며, 메모리 또한 충분히 처리할 수 있는 크기만큼만 차지하기 때문이다.