[Prime Number] 에라토스테네스의 체 (소수 찾기)

소수 판별법의 일종으로, 2부터 N까지의 자연수를 나열하고 2의 배수, 3의 배수, N//2 의 배수를 찾아가며 지워간다. 이후 남는 숫자가 2~N사이의 소수이다.

 

APS에 심심치 않게 볼수 있는 소수를 찾는 방법 중하나이다. 중~하 문제에서 많이 나오기때문에 꼭 숙지하는 것이 좋다.소수는 약수가 1과 자기자신만 가지고 있는 숫자를 말한다. 소수를 찾는 방법은 직접 약수를 찾아가면서 소수인지 아닌지 확인하는 방법이 있다. 하지만 숫자에 범위에 따라 상황에 맞는 방법을 선택하면 실행속도가 더 빠르기 때문에 이 방법도 알아두는 것이 좋다.

 

개요

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
3. 자기 자신을 제외한 2의 배수를 모두 지운다.
4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
5. 자기 자신을 제외한 3의 배수를 모두 지운다.
6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
7. 자기 자신을 제외한 5의 배수를 모두 지운다.
8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
9. 자기 자신을 제외한 7의 배수를 모두 지운다.
10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

 

설명

약수가 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]