[알고리즘/Python] 에라토스테네스의 체

 

에라토스테네스의 체

-> 여러 개의 수가 소수인지 아닌지를 판별할 때 사용하는 대표적인 알고리즘.

-> N보다 작거나 같은 모든 소수를 찾을 때 사용할 수 있다.

• 소수란? 1과 자신 자신 외의 약수를 가지지 않는 1보다 큰 자연수를 말한다.

---

> 동작 과정

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

이미지 출처 - 위키백과

---

> 장단점

에라토스테네스의 체 알고리즘의 시간 복잡도는 O(NloglogN)으로 사실상 선형 시간에 동작할 정도로 빠르다.

그래서 다수의 소수를 찾아야 하는 문제에서 자주 사용된다.

하지만 알고리즘을 수행할 때 N의 크기만큼 리스트를 할당해야 하기 때문에 메모리가 많이 필요하다는 단점이 있다.

또한 10억이 소수인지 찾아야 하는 문제에서는 에라토스테네스의 체를 이용하기 어렵다.

---

파이썬 코드로 구현하면 이렇게 된다.

코드 1.

n=1000
a = [False,False] + [True]*(n-1)
primes=[]

for i in range(2,n+1):
  if a[i]:
    primes.append(i)
    for j in range(2*i, n+1, i):
        a[j] = False
print(primes)

 

코드 2.

import math

n = 1000 # 2부터 1,000까지의 모든 수에 대하여 소수 판별
array = [True for i in range(n + 1)] # 처음엔 모든 수가 소수(True)인 것으로 초기화

# 에라토스테네스의 체 알고리즘 
for i in range(2, int(math.sqrt(n)) + 1): # 2부터 n의 제곱근까지의 모든 수를 확인하며
    if array[i] == True: # i가 소수인 경우 (남은 수인 경우)
        # i를 제외한 i의 모든 배수를 지우기
        j = 2 
        while i * j <= n:
            array[i * j] = False
            j += 1

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

---

관련 문제

https://www.acmicpc.net/problemset?sort=ac_desc&algo=67 

문제 - 1 페이지

 

 

 

 

출처-

https://freedeveloper.tistory.com/392

https://velog.io/@mmy789/Algorithm

https://wikidocs.net/21638