[알고리즘] 파이썬으로 에라토스테네스의 체를 이용해 소수 판별하기 | Python, Algorithm, Prime Number

에라토스테네스의 체는 고대 그리스의 수학자 에라토스테네스가 발견한 소수(prime number)를 찾는 방법입니다. 수학시간은 아니므로 소수냐 합성수냐에 대한 정의 설명은 생략하고, 어떤 방식으로 동작하는지 살펴보겠습니다.

 

1. 소수를 찾고자 하는 구간의 모든 수를 나열합니다.

2. 어느 한 소수의 배수를 모두 지웁니다.

3. 남아있는 수 가운데 다음 소수를 찾습니다. 

4. 2-3 과정을 반복합니다.

 

여기서 2가지 포인트가 있습니다. 먼저, 위 과정에서 2단계의 최초 시작은 2부터 합니다. (왜냐하면 1은 소수도 합성수도 아닌 수이기 때문입니다) 그다음은 3, 5, 7.... 순으로 커지게 됩니다. 

 

두번째는 최대 약수는 어느 숫자의 제곱근을 넘을 수 없다는 사실입니다. 정수론 시간이 아니므로 엄밀한 증명은 넘어가더라도, 제곱근 값을 넘어가게 된다면 나머지 다른 약수는 제곱근보다 작은 숫자일 것입니다. 작은 숫자는 이미 카운트가 됐을 것이므로, 따라서 제곱근을 넘을 수 없는 것으로 셀 수 있을 것입니다.

 

이를 코드로 구현하면 다음과 같습니다.

 

# 에라토스테네스의 체
def eratos(n):
    sieve = [True] * n
    gcd = int(n ** 0.5)

    for i in range(2,  gcd+1):
        if sieve[i] == True:
            for j in range(i+i, n, i):
                sieve[j] = False   
    return [i for i in range(2, n) if sieve[i] == True]

print(eratos(20))

 

아래 사진을 보면, 잘 동작하는 것을 확인할 수 있습니다.

---

참고:

 

1. Wikipedia, "에라토스테네스의 체" 

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전