에라토스테네스의 체 - 소수를 구하는 방법

소수(Prime Number)란?

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

 

코드로 보면

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

 

 

알고리즘 개선

예를 들어 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일 때는 위의 알고리즘으로 모든 수를 하나씩 검사하는 것으로는 느릴 수 있다.

def is_prime_number(x):
    for i in range(2,int(x**0.5)+1):
        if x%i==0:
            return False
    return True
    
#math 함수를 쓰지 않았을 때

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

에라토스테네스의 체

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

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

그림을 통한 예시

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

1. 초기 단계에서는 다음과 같이 2부터 26까지의 모든 자연수를 나열합니다.
   
2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수를 찾은 다음, 그 수를 제외한 배수를 제거합니다. 따라서 2를 제외한 2의 배수는 모두 제외합니다.
   
3. 남은 수 중에서 아직 처리하지 않은 가장 작은 수를 찾은 다음, 그 수를 제외한 배수를 제거합니다. 따라서 3을 제외한 3의 배수는 모두 제외합니다.
   
4. 남은 수 중에서 아직 처리하지 않은 가장 작은 수를 찾은 다음, 그 수를 제외한 배수를 제거합니다. 따라서 5를 제외한 5의 배수는 모두 제외합니다.
   
5. 이어서 마찬가지로, 남은 수 중에서 가장 작은 수를 찾은 다음, 그 수를 제외한 배수를 제거하는 과정을 반복합니다. 이 과정을 거쳐 남아 있는 수는 모두 소수이며, 이렇게 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만 번 정도의 연산으로 문제를 해결할 수 있으며, 메모리 또한 충분히 처리할 수 있는 크기만큼만 차지하게 됩니다.