소수 판별 알고리즘 - 에라토스테네스의 체

📃에라토스테네스의 체

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

🌓 특징

• 2~n까지의 숫자에서 숫자들의 배수를 모두 제거한 뒤 제거되지 않은 숫자를 소수로 판별하는 방식
• 실제 계산은 무식하지만 프로그래밍에선 상당히 효율적인 방법론
• 구하자고하는 수의 √(n)에 해당하는 소수의 배수만 확인하여 지우면 되기 때문에 빠름

👏 과정(예시 : 2~120까지 모든 소수 찾기)

1. 2~120까지의 숫자 나열
2. 2는 소수이므로 오른쪽에 2를 쓰고 2의 배수를 모두 지움
3. 남아있는 숫자에서 3은 소수이므로 오른쪽에 3을 쓰고 3의 배수를 모두 지움
4. 남아있는 숫자에서 5는 소수이므로 오른쪽에 5을 쓰고 5의 배수를 모두 지움
5. 남아있는 숫자에서 7은 소수이므로 오른쪽에 7을 쓰고 7의 배수를 모두 지움
6. 위 과정을 반복
7. 남아있는 수의 집합 = 소수의 집합

👀 그래서 이걸 왜쓰는데?

• 특정 범위 내에서 모든 소수를 찾아야 할 경우에 가장 좋은 효율의 방식
• 대량의 소수를 한꺼번에 판별할 경우 다른 소수를 찾는 방식에 비해 가장 빠르게 찾을 수 있는 방법 (시간 복잡도 ↓)
• 다만 특정 범위 내의 소수를 판정하는 데에만 효율적
• 메모리를 많이 잡아먹는 단점이 있음

✔ 각 방식의 시간 복잡도

1. 하나부터 전부 2~N-1까지 나눠버려 하나라도 나눠떨어지는가 확인하는 방법 (시간 복잡도 O(N))
2. N의 약수는 무조건 √(N)의 범위에 존재하는 것을 이용하는 방법 (채가을님이 설명) (시간복잡도 O(√(N)))
3. 에라토스테네스의 체 시간복잡도 O(nlog(logn)))

👍이럴때 사용합시다

• 알고리즘을 푸는데 시간 초과 걸리는 경우

• 메모리가 넉넉할 경우
• 주어지는 N의 값이 1,000,000 이하 수준일 경우

반응형

⚙코드 예시

def prime_list(n):
    # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
    array = [True] * n

    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if array[i] == True:           # i가 소수인 경우 
            for j in range(i+i, n, i): # i이후 i의 배수들을 False 판정
                array[j] = False

    # 소수 목록 산출
    return [i for i in range(2, n) if array[i] == True]