소수의 판별

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

알고리즘

간단한 방법

• X를 2부터 X-1까지의 모든 자연수로 나누어보고 나누어 떨어지는 수가 하나라도 존재하면 소수가 아니다.
• 코드를 작성해보면 다음과 같다.

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)) # False
print(is_prime_number(7)) # True

• 위와 같은 방법은 모든 수에 대해 하나씩 나누어야 하기 때문에 시간복잡도는 $O(X)$
  • 1,000,000이라는 숫자를 소수인지 확인하려면 1,000,000을 2부터 999,999까지의 모든 수에 대하여 하나씩 나누어야 하므로 매우 비효율적

개선된 알고리즘

• 자연수의 약수가 가지는 특징을 이용하여 개선된 알고리즘을 작성해보자.
• 자연수는 모든 약수에 대하여 가운데 약수를 기준으로 대칭적인 형태를 보인다.
  • 예를 들어 16의 약수 1, 2, 4, 8, 16이다.
  • 모든 약수에 대하여 가운데 약수 4를 기준으로 대칭적으로 2개씩 앞뒤로 묶어 곱하면 16을 만들 수 있다.
• 우리는 특정한 자연수 X가 소수인지 확인하기 위하여 바로 가운데 약수(제곱근)까지만 나누어떨어지는지 확인하면 된다.
  • 위의 예시에서는 4까지만 확인하면 된다.
• 코드로 작성하면 다음과 같다. (출처)

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 # 소수임

print(is_prime_number(4)) # 4는 소수가 아님
print(is_prime_number(7)) # 7은 소수임

• 개선된 소수 판별 알고리즘은 제곱근까지만 확인하면 되기 때문에 시간 복잡도는 $O(X^{1/2})$

하나의 수에 대해서 소수인지 아닌지 판별하는 함수를 작성해보았다.
하지만 소수인지 아닌지 판별해야하는 경우가 아니라, 수의 범위가 주어졌을 때, 그 전체 수의 범위 안에서 존재하는 모든 소수를 찾아야 하는 경우에는 어떻게 해야할까?

에라토스테네스의 체

• 에라토스테네스의 체 알고리즘은 여러 개의 수가 소수인지 아닌지를 판별할 때 사용하는 대표적인 알고리즘이다.
  • N보다 작거나 같은 모든 소수를 찾을 때 사용할 수 있다.

알고리즘

에라토스테네스의 체 알고리즘은 다음과 같다.
1. 2부터 N까지의 모든 자연수를 나열한다.
2. 남은 수 중에서 아직 처리하지 않은 가장 작은수 i를 찾는다.
3. 남은 수 중에서 i의 배수를 모두 제거한다. (i는 제거하지 않는다.)
4. 더 이상 반복할 수 없을 때까지 2번과 3번 과정을 반복한다.

그림으로 이해하기

N = 26 이라 가정하고 그림을 그려 이해해보자.

STEP 0

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

STEP 1

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

STEP 2

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

STEP 3

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

STEP 4

• 남은 수 증에서 가장 작은 수를 찾은 다음 그 수를 제외한 배수를 제거하는 과정을 반복한다.
• 이 과정을 거쳐 남아있는 수는 모두 소수이며 이렇게 2부터 26까지의 모든 소수를 찾았다.

코드 작성하기

• 매 스텝마다 남은 수 중에서 아직 처리하지 않은 가장 작은 수를 찾을 때, i는 N의 제곱근(가운데 약수)까지만 증가시켜 확인한다.
• 코드로 작성하면 다음과 같다. (출처)

import math

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

# 에라토스테네스의 체 알고리즘 
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의 크기만큼 리스트를 할당해야하기 때문에 메모리가 많이 필요하다는 단점이 있다.
• 따라서 에라토스테네스의 체를 이용하는 문제의 경우 N이 1,000,000이내로 주어지는 경우가 많다.

📍 References

• 이것이 취업을 위한 코딩테스트다. - 나동빈 저
  https://www.youtube.com/watch?v=5ypkoEgFdH8