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

# 소수 (Prime Number) 판별 알고리즘

 소수란 1보다 큰 자연수 중 1과 자기자신을 제외한 자연수로는 나누어떨어지지 않는 자연수를 말한다. 코딩 테스트에서는 어떠한 자연수가 소수인지 아닌지 판별해야 하는 문제가 자주 출제되므로 알고리즘을 기억해두면 좋다.

 

 다음은 기본적인 소수 판별 알고리즘을 파이썬으로 구현한 것이다.

# 소수 판별 함수 정의 (2이상의 자연수에 대하여)
def is_prime_number(x):
    # 2부터 (x - 1)까지의 모든 수를 확인하며
    for i in range(2, x):
        # x가 해당 수로 나누어떨어진다면
        if x % i == 0:
            return False  # 소수가 아님
    return True  # 소수임


print(is_prime_number(4))
print(is_prime_number(7))

 기본적인 소수 판별 알고리즘의 시간 복잡도는 O(N)이다. 2부터 N - 1까지의 모든 자연수에 대하여 차례차례로 연산을 수행하기 때문이다. 다만, 자연수의 범위가 10억과 같이 커진다면 연산 수행에 문제가 생기므로 시간복잡도를 개선할 필요성이 있다.

 

# 개선된 소수 판별 알고리즘

 약수의 성질에서 시간 복잡도 개선의 단서를 찾을 수 있다. 어떤 한 수에 대한 모든 약수는 가운데 약수를 기준으로 곱셈 연산에 대해 대칭을 이룬다. 예를 들어, 16의 약수 1, 2, 4, 8, 16에서 2 X 8 = 16이고 8 X 2 = 16이다. 즉, 특정한 수에 대한 모든 약수를 찾을 때 가운데 약수(제곱근)까지만 확인하면 충분하다. 

 

 다음 코드는 이를 활용하여 소수 판별 알고리즘을 개선한 형태이다.

# 소수 판별 함수 (2이상의 자연수에 대하여)
def is_prime_number(x):
    # 2부터 x의 제곱근까지의 모든 수를 확인하며
    for i in range(2, int(x ** 0.5) + 1):
        # x가 해당 수로 나누어 떨어진다면
        if x % i == 0:
            return False  # 소수가 아님
    return True  # 소수임


print(is_prime_number(4))
print(is_prime_number(7))

 이 경우 특정 수의 제곱근까지만 확인하는 과정이므로, 시간 복잡도는 O(√N)이 된다.(루트 N)

 

# 에라토스테네스의 체 알고리즘

 지금까지 특정 수에 대하여 소수를 판별하는 과정을 살펴보았다. 더 나아가 만일 특정한 수의 범위가 주어지고 그 범위안의 존재하는 모든 소수를 찾아야 한다면 어떻게 해야할까? 이 상황에서는 다수의 자연수에 대하여 소수 여부를 판별하는 대표적 알고리즘인 에라토스테네스의 체를 사용할 수 있다. 에라토스테네스의 체 알고리즘의 동작 과정은 다음과 같다.

 

  2번 단계에서는 남은 수 중에서 아직 처리하지 않은 가장 작은 소수 i(남은 수가 결국 소수)를 찾고, 3번 단계에서 i를 제외한 그 i의 배수를 모두 제거하는 과정을 반복한다.

 

 다음은 N=26인 상황일 때의 동작과정이다.

 

 에라토스테네스의 체 역시 약수의 성질을 적용할 수 있다. 예를 들어, 위 경우는 26의 대략적인 제곱근인 5까지만 확인하면 된다. 6부터는 배수가 5를 넘어갈 수 없고, 이미 앞에서 소수 2, 3, 5의 배수를 제거했기 때문이다. 따라서, √N까지의 자연수만 확인해도 동일한 결과를 얻을 수 있다.

 

 다음은 에라토스테네스의 체 알고리즘을 파이썬 코드로 구현한 것이다.

n = 1000  # 2부터 1000까지의 모든 수에 대하여 소수 판별
# 처음엔 모든 수를 소수(True)인 것으로 초기화(0, 1은 제외)
array = [True for i in range(n + 1)]

# 에라토스테네스의 체 알고리즘 수행
# 2부터 n의 제곱근까지의 모든 수를 확인하며
for i in range(2, int(n ** 0.5) + 1):
    if array[i] == True:
        # i를 제외한 i의 모든 배수를 지우기
        j = 2
        while i * j <= n:
            array[i * j] = False
            j += 1

# 모든 소수 출력
for i in range(2, n + 1):
    if array[i]:
        print(i, end=' ')

 이러한 에라토스테네스의 체 알고리즘의 시간 복잡도는 O(NloglogN)으로 선형시간에 가까울 정도로 매우 빠르므로, 다수의 소수를 찾는 문제에서 효율적이다. 다만, 각 자연수에 대한 소수 여부를 저장해야 하기 때문에 메모리가 많이 필요하다는 단점이 있다. 예를 들어, N이 10억인 경우 문제 해결이 어렵다.

 

 

본 포스팅은 '안경잡이 개발자' 나동빈 님의 저서

'이것이 코딩테스트다'와 그 유튜브 강의를 공부하고 정리한 내용을 담고 있습니다.