[ Algorithm ] 에라토스테네스의 체 ( Python )( 소수를 구하는 방법)

<  에라토스테네스의 체(Sieve of Eratosthenes) 란 ? >

고대 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법이다. 

이 방법은 체로 치듯이 수를 걸러낸다고 해서 '에라토스테네스의 체' 라고 불린다.

소수를 구하는 방법은 여러가지가 존재하지만 이 방식을 이용하면 보다 효과적으로 소수를 빠르게 구할 수 있다.

 

 

< 에라토스테네스의 체 원리, 사용 방법 , 알고리즘 >

먼저 나무위키, 위키백과의 그림을 참고하자.

 

 

간단히 위 그림을 설명하자면  1과, 2, 3, 5, 7의 배수인 수들을 모두 제거하면 소수만 남게 된다.

어떻게 이런 방식을 사용할 수 있을까?  라는 질문이 나올 수 있다.

 

우선 소수에 대해 알아 볼 필요가 있다.

소수란 1과 자기 자신 이외에 약수를 가지는 합성수이다.  그렇다면 여기서 위의 원리를 유추할 수 있다.

즉 1과 자기 자신 이외에 약수를 가지게 되는 경우를 제거해야 소수가 되기 때문에

1을 예외로 제거하고 2, 3, 5, 7 의 배수를 제거하면 결국 남는건 소수 뿐이다 라는 것을 알 수 있다.

그림의 경우, 11**2 >120 이므로 11보다 작은 수의 배수들만 지워도 충분하다. 즉, 120보다 작거나 같은 수 가운데 2, 3, 5, 7의 배수를 지우고 남는 수는 모두 소수다.

 

 

자세한 ( 알고리즘 진행 방식 )은 아래와 같다.

1.  2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.  그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.

2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)

3. 자기 자신을 제외한 2의 배수를 모두 지운다.

4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)

5. 자기 자신을 제외한 3의 배수를 모두 지운다.

6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)

7. 자기 자신을 제외한 5의 배수를 모두 지운다.

8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)

9. 자기 자신을 제외한 7의 배수를 모두 지운다.

10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

 

위 알고리즘을 ( 프로그래밍으로 표현 )한건 아래와 같다. 

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

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

[ Python (3.64 )]

def prime_list(n):
    sieve = [True] * n
    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if sieve[i] == True:         
            for j in range(2*i, n, i):
                sieve[j] = False

    return [i for i in range(2, n) if sieve[i] == True]

 

실행 예시

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

 

위 코드를 한줄씩 차근차근 해석해 보고자 한다.

 

def prime_list(n):
    sieve = [True] * n

처음시작은 정해지지 않았고 n 번까지 소수를 출력하고자 한다. 

우선 체로 거르기 전 모든 수를 나열하기 위해 sieve = [True] * n 을 썼다. 

 

   m = int(n ** 0.5)
    for i in range(2, m + 1):

위에서도 말했듯이 배수들로 소수를 걸러야 하는데 이때 최대 배수를 선정하는 기준은 m= int(n ** 0.5 )를 넘기지 않아야 함. 그래야 구하고자 하는 수까지 반복 낭비 없이 이용됨

예) n = 10 일때 m 사용 없이

for i in range(2, n+1):

로 사용하게 되면 m을 사용한 위와 달리 4, 5, 6, 7, 8, 9, 10의 배수를 False로 바꿀텐데 이것들은 m을 사용하면 벌써 제거될 배수들이기 때문에 반복을 낭비하는 꼴이 된다.

즉,  나열된 수를 제거하는 최대의 배수는  무조건 n의 제곱근을 이하이므로 제거할 합성수를 for i in range(2, m+1)로 i (제거할 숫자들의 배수들, 예를 들어 위에선 2,3,5,7)를 제한시킨다. 이때 최소한 2의 배수부터 제거 시켜야 하기 때문에 range에 2 들어감.

 

        if sieve[i] == True:         
            for j in range(2*i, n, i):
                sieve[j] = False

나열된 수의 위치(i) 가 True이면 2*i부터 n까지 i 만큼 커지면서 sieve[j] 자리의 값을 False로 만든다.

즉, 배수 자기 자신(예를들어 2, 3, 5, 7) 은 남겨둬야하기 때문에 2*i 부터 i씩 커지면서 소수 아닌 수를 제거해 나간다.

이렇게 하면 합성수들의 자리는 False로 바뀌고 배수의 자리는 True로 남는다.

 

    return [i for i in range(2, n) if sieve[i] == True]

위의 문장은 아래 코드와 같은 의미.

return = []
for i in range(2, n):
    if sieve[i] == True:
        result.append(i)

for문의 리스트 내포형식으로 https://wikidocs.net/15 참고하면 좋다.

위 과정으로 True 자리에는 숫자 i가 대입되게 되고 return 하면 소수가 출력된다.

 

 

** 제가 잘못 이해하고 있거나 그러면 댓글로 알려주시면 최대한 빠른시일 내에 고치도록 하겠습니다.  **