참조
이것이 취업을 위한 코딩 테스트다 with 파이썬을 읽고 작성하였습니다.

소수의 판별

소수(Prime Number)란 2보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어떨어지지 않는 자연수입니다. 예를 들어 '6'은 1,2,3,6으로 나누어 떨어져서 소수가 아니고 '7'은 1과 7을 제외하고는 나누어 떨어지지 않아서 소수입니다.

간단한 방법

해당 수가 소수인지를 판별하는 가장 간단한 방법은 X가 주어졌을 때 X를 2부터 X - 1까지의 모든 수로 나누어 보는 것입니다. 만약 2부터 X-1까지의 모든 자연수로 나누었을 때 나누어떨어지는 수가 하나라도 존재하면 X는 소수가 아닙니다.

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))

이 방법은 만약 1,000,000이라는 수가 소수인지 판별하려면 1,000,000을 2부터 999,999까지의 모든 수에 대하여 하나씩 나누어야 합니다. 즉 시간 복잡도가 O(X)이기에 몹시 비효율적입니다.

알고리즘 개선

위의 알고리즘을 개선할 수 있는데 예시를 통해 알아보겠습니다.

예를 들어 16이라는 수의 약수는 다음과 같습니다.

• 1 X 16 = 16
• 2 X 8 = 16
• 4 X 4 = 16
• 8 X 2 = 16
• 16 X 1 = 16

여기서 알 수 있는 점은 가운데 약수를 기준으로 각 등식이 대칭적인 형태를 보인다는 것입니다.
예를 들어 2 X 8 = 16은 8 X 2 = 16과 대칭입니다. 그렇기에 특정한 자연수 X가 소수인지 확인하기 위하여 바로 가운데 약수까지만 '나누어떨어지는지' 확인하면 됩니다. 다시 말해 제곱근까지만(가운데 약수까지만) 확인하면 된다는 점을 기억해야 합니다.

import math

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

개선된 소수 판별 알고리즘의 시간 복잡도는 제곱근까지만 확인하면 되기에 시간 복잡도가 O(X의 2분의 1승)이 됩니다. 그런데 만약 소수인지 아닌지 판별해야 되는 수가 1,000,000일 때는 위의 알고리즘으로 모든 수를 하나씩 검사하는 것으로는 느릴 수 있습니다.

에라토스테네스의 체

에라토스테네스의 체 알고리즘은 여러 개의 수가 소수인지 아닌지를 판별할 때 사용하는 대표적인 알고리즘입니다. 에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾을 때 사용할 수 있습니다. 아래와 같은 과정을 통해 수행합니다.

1. 2부터 N까지의 모든 자연수를 나열한다

2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다

3. 남은 수 중에서 i의 배수를 모두 제거한다(i는 제거하지 않는다)

4. 더 이상 반복할 수 없을 때까지 2번과 3번 과정을 반복한다.

그림을 통한 예시

만약 N이 26일 때를 그림을 통해 알아보겠습니다. 알고리즘에 따라서 먼저 2부터 26까지의 모든 자연수를 나열합니다. 그 뒤에 알고리즘을 수행하면 됩니다.

0. 초기 단계에서는 다음과 같이 2부터 26까지의 모든 자연수를 나열합니다.
   

1. 남은 수 중에서 아직 처리하지 않은 가장 작은 수를 찾은 다음, 그 수를 제외한 배수를 제거합니다. 따라서 2를 제외한 2의 배수는 모두 제외합니다.
   

2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수를 찾은 다음, 그 수를 제외한 배수를 제거합니다. 따라서 3을 제외한 3의 배수는 모두 제외합니다.
   

3. 남은 수 중에서 아직 처리하지 않은 가장 작은 수를 찾은 다음, 그 수를 제외한 배수를 제거합니다. 따라서 5를 제외한 5의 배수는 모두 제외합니다.
   

4. 이어서 마찬가지로, 남은 수 중에서 가장 작은 수를 찾은 다음, 그 수를 제외한 배수를 제거하는 과정을 반복합니다. 이 과정을 거쳐 남아 있는 수는 모두 소수이며, 이렇게 2부터 26까지의 모든 소수는 아래와 같습니다.
   

코드

위의 예시에서 매 스텝마다 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다고 하였으나, 이때 개선된 소수 판별을 생각해 i는 N의 제곱근(가운데 약수)까지만 증가시켜 확인하면 됩니다.

import math

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

# 에라토스테네스의 체 알고리즘
for i in range(2, int(math.sqrt(n)) + 1): # 2부터 n의 제곱근까지의 모든 수를 확인하며
    if array[i] == True: # i가 소수인 경우(남은 수인 경우)
        # 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이 1,000,000이라고 하면 NloglogN은 약 4,000,000 정도입니다.

다만, 메모리가 많이 필요하다는 단점이 있습니다. 알고리즘을 수행할 때 N의 크기만큼 리스트를 할당해야 하기 때문입니다. 예를 들어 N = 1,000,000일 때는 2부터 1,000,000까지의 모든 수에 대한 정보를 담을 수 있는 크기의 리스트가 필요합니다. 또한 10억이 소수인지 찾는 문제에서는 에라토스테네스의 체를 이용하기 어렵습니다.

따라서 에라토스테네스의 체를 이용해야 되는 문제의 경우 N이 1,000,000 이내로 주어지는 경우가 많습니다. 그렇게 하면 이론상 400만 번 정도의 연산으로 문제를 해결할 수 있으며, 메모리 또한 충분히 처리할 수 있는 크기만큼만 차지하게 됩니다.