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)
여러 개의 수가 소수인지 아닌지를 판별할 때 사용하는 대표적인 알고리즘
동작 원리
- 2부터 N까지의 모든 자연수를 나열한다.
- 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다.
- 남은 수 중에서 i의 배수를 모두 제거한다. (i는 제거하지 않는다.)
- 더 이상 반복할 수 없을 때까지 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
'이것이 코딩테스트다'를 읽고 공부한 내용을 바탕으로 작성하였습니다.
'Python > 이것이 코딩테스트다' 카테고리의 다른 글
[Python] 6. 순열과 조합 (0) | 2022.11.14 |
---|---|
[Python] 5. 구간 합 계산 (0) | 2022.11.14 |
[Python] 4. 투 포인터 (0) | 2022.11.11 |
[Python] 2. 주요 라이브러리 (1) | 2022.11.09 |
[Python] 1. 복잡도 (0) | 2022.11.08 |