[학습] 에라토스테네스의 체 (소수 판별 알고리즘)

에라토스테네스의 체는 소수 판별 알고리즘으로 소수를 대량으로 빠르게 구할 때 사용된다.

먼저 소수 판별법을 알아보자.

코드 1

import sys
input = sys.stdin.readline

def is_prime_number(n):
    for i in range(2, n):
        if n % i == 0:
            print("소수가 아닙니다.")
            break
    else:
        print("소수가 맞습니다.") 

N = int(input())

if N == 0 or N == 1:
    print("소수가 아닙니다.")
else:
    is_prime_number(N)

첫번째 코드의 시간 복잡도는 O(n) 이다.
소수의 정의를 그대로 사용하였다. 1과 자신외에는 나누어 떨어지는 수가 없다.
하지만 코드 1은 매우 비효율적이다. 개선한 코드를 살펴보자.

코드 2

import sys
input = sys.stdin.readline

def is_prime_number(n):
    for i in range(2, (int)(n ** 0.5 + 1)):
        if n % i == 0:
            print("소수가 아닙니다.")
            break
    else:
        print("소수가 맞습니다.") 

N = int(input())

if N == 0 or N == 1:
    print("소수가 아닙니다.")
else:
    is_prime_number(N)

어떠한 수의 약수는 제곱근을 기준으로 짝을 이룬다.
즉, N을 입력받았다면 N까지 검사할 필요없이 N의 제곱근까지만 나누어 떨어지는지 확인해주면 된다.
이렇게 할 경우 시간 복잡도는 O(n) -> O(n^0.5)로 줄어들게 된다.

하지만 만약 0 ~ N까지 범위 내에 소수의 개수를 구한다고 해보자.
위의 방식으로 0 ~ N까지 for문을 돌면서 하나하나 소수가 맞는지 판별을 하게 되면 꽤 오랜시간이 걸릴 것이다.
이럴 때 에라토스테네스의 체를 사용하면 된다.

코드 이전에 에라토스테네스의 체의 개념을 간단히 알아보자.

에라토스테네스의 체는 소수 판별을 원하는 범위만큼의 배열을 미리 만들어두고 특정 수의 배수를 지워나가는 방식이다.
마지막까지 지워지지 않은 수가 소수이다.

코드 3 (에라토스테네스의 체)

import sys
input = sys.stdin.readline

# 0 ~ N까지의 수 중 소수를 모두 출력
def prime_number_sieve(max):
    arr = [i for i in range(max + 1)]
    
    for i in range(2, max + 1):
        # 이미 지워졌다면 넘어감
        if arr[i] == 0: continue

        # 현재 수는 제외하고 배수만큼 지워나감
        for j in range(2 * i, max + 1, i):
            arr[j] = 0

    # 소수 출력
    for i in range(2, max + 1):
        if arr[i] != 0:
            print(arr[i], end = ' ')

N = int(input())
prime_number_sieve(N)

• 원하는 크기만큼 배열을 만들고 인덱스를 값으로 채워넣는다.
• 2부터 자기 자신은 제외하고 배수를 지워나간다.
• 이미 지워져있다면 넘어간다.

대량의 소수를 판별하고 싶다면 에라토스테네스의 체를 이용하는것이 시간 복잡도면에서 좋다.