[Python] 3. 에라토스테네스의 체

1. 소수(Prime Number)

2보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어 떨어지지 않는 자연수

ex) 2, 7...

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

print(is_prime_number(4))
print(is_prime_number(7))
# False
# True

위 코드의 시간복잡도는 O(X)이며, 비효율적이다. 예를들어, 1,000,000이라는 수가 소수인지 확인해야 할 때는 1,000,000을 2부터 999,999까지의 모든 수에 대하여 하나씩 나누어야 한다.

이 알고리즘을 개선해서 시간복잡도가 O(X)보다 더 빠르게 동작하도록 작성해 보자. 자연수의 약수가 가지는 특징을 파악하고 있다면 그 원리를 쉽게 이해할 수 있다. 

16이라는 수의 약수(Divisor)는 다음과 같다. 

• 1, 2, 4, 8, 16

이때 모든 약수에 대해, 가운데 약수를 기준으로 하여 대칭적으로 2개씩 앞뒤로 묶어서 곱하면 16을 만들 수 있다. 

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

여기서 알 수 있듯이, 약수를 기준으로 각 등식이 대칭적인 형태를 보인다. 

8이라는 숫자 하나 더 예시를 들어보자. 

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

예시로 든 16과 8의 경우를 보면, 각 등식이 대칭적인 형태를 보이고, 따라서 제곱근까지만 확인하면 된다는 것을 알 수 있다. 

그렇다면 math 라이브러리의 sqrt 함수를 이용해 제곱근까지만 확인하는 코드를 작성해보자. 

import math

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

print(is_prime_number(4))
print(is_prime_number(7))
# False
# True

제곱근까지만 확인하면 되기 때문에 시간복잡도가 O(X) 에서 O(X**½)인 것을 알 수 있다. 

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

 

 

2. 에라토스테네스의 체(Eratosthenes Sieve) 

여러 개의 수가 소수인지 아닌지를 판별할 때 사용하는 대표적인 알고리즘

동작 원리

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

import math

n = 1000 # 2부터 1,000까지의 모든 수에 대하여 소수 판별
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가 소수인 경우(남은 수인 경우)
        j = 2 # i를 제외한 i의 모든 배수를 지우기
        while i * j <= n:
            array[i * j] = False
            j += 1
            
# 모든 소수 출력
for i in range(2, n + 1):
    if array[i]:
        print(i, end=' ')
        
# 2 3 5 7 11 13 17 19 23 29 ... 953 967 971 977 983 991 997

에라토스테네스의 체 알고리즘의 시간 복잡도는 O(NloglogN)으로 사실상 선형 시간에 동작할 정도로 빠르다. 예를 들어 N =1,000,000 일 때 약 4,000,000 정도가 될 것이다. 

이처럼 에라토스테네스의 체 알고리즘은 매우 빠르게 동작하기 때문에 다수의 소수를 찾아야 하는 문제에서 자주 사용된다. 하지만, 메모리가 많이 필요하다는 단점이 있는데, 알고리즘을 수행할 때 N의 크기만큼 리스트를 할당해야 하기 때문이다. 예를 들어 N = 1,000,000 일 때는 2부터 1,000,000 까지의 모든 수에 대한 정보를 담을 수 있는 크기의 리스트가 필요하다. 따라서, N < 1,000,000 일 경우에 사용하도록 하자. 

참고자료 : 코린아 코딩하자 https://www.youtube.com/watch?v=fT4XQMa4-8M&t=9s 

 

 

 

'이것이 코딩테스트다'를 읽고 공부한 내용을 바탕으로 작성하였습니다.