알고리즘 문제를 풀다보면 특정 수들이 소수인지 판단하도록 요구하는 문제들이 줄곧 있다.
아예 대놓고 소수찾기라는 문제만 쳐봐도 꽤 많은 문제들이 나올 것이다.
소수는 영어로 Prime Number라고 부르며 1과 자기자신 외에는 어떠한 수로도 나누어 떨어지지 않는 수를 말한다.
특정 수 N이 소수인지 아닌지 구하는 법은 바로 이 특징을 활용하여 2부터 N-1 까지의 수로 해당 수를 나눠보고, 이 과정에서 어떠한 수에 의해 나누어 떨어지는지 확인하는 것이다.
나누어떨어지지 않는다면 해당 수는 소수인 것이고, 도중에 다른 수에 의해 나누어 떨어진다면 그 수는 소수가 아닐 것이다.
이를 코드로 표현하면 다음과 같다.
def is_prime_num(n):
for i in range(2, n):
if n % i == 0:
return False # i로 나누어 떨어지면 소수가 아니므로 False 리턴
return True # False가 리턴되지 않고 for문을 빠져나왔다면 소수이므로 True 리턴
위 방식은 입력값으로 받는 숫자 X에 대하여 2 ~ X-1번까지, 즉 X-2번의 연산이 필요하며 이는 시간복잡도 O(x)로 표현할 수 있겠다.
하지만 우리는 약수의 특성을 활용해서 이 연산 횟수를 반으로 줄여줄 수 있다.
여기서 말하는 약수의 특성이란, 특정 수 N의 약수들을 일렬로 나열했을 때 그 중 가운데의 수를 중심으로 약수가 대칭된다는 것이다.
16을 예로 들어보자.
16의 약수들을 일렬로 나열하면 1, 2, 4, 8, 16이 된다.
중간값 4를 기준으로 양 옆을 보면 약수들이 서로 대칭되고 있음을 확인할 수 있다. (1 * 16 = 16 * 1, 2 * 8 = 8 * 2)
다시말해, 만약 우리가 16의 약수를 찾고 싶다면 16의 약수의 중간값을 기준으로 한 쪽만 검사를 하더라도 다른 쪽의 약수들을 알 수 있다.
여기서 중간값은 찾고자하는 수의 제곱근 값으로 가정해 처리할 수 있으며, 이 제곱근 값을 기준으로 왼쪽에 약수가 하나도 존재하지 않는다면 제곱근 값 기준 오른쪽에도 약수가 존재하지 않는다고 확신할 수 있다.
이를 통해 우리는 기존 for문이 2에서 N-1까지 돌았던 것을 2에서 N의 제곱근까지만 돌도록 처리해주어 연산 횟수를 절반에 가깝게 줄여줄 수 있다.
이 방식으로 접근했을 때 작성한 코드는 다음과 같다.
# 제곱근을 구하기 위해 math 라이브러리 임포트
import math
def is_prime_num(n):
for i in range(2, int(math.sqrt(n))+1): # n의 제곱근을 정수화 시켜준 후 + 1
if n % i == 0:
return False
return True
에라토스테네스의 체
우리는 위에서 특정 수 N이 주어졌을 때, 그 수가 소수인지 아닌지 판별하는 방법을 알아봤다.
그런데 만약 여러 개의 수에 대하여 소수 판별을 해줘야하는 상황이라면 어떨까?
예컨대 100 ~ 300 사이의 모든 소수들을 구해야하는 상황이라면 우리는 위의 방식을 이용해 하나하나 모든 수들을 판별해줘야할까?
계산에 소요되는 시간과 수고스러움을 생각해봤을 때 다른 방법이 필요해보인다.
그리고 이 상황에서 사용할 수 있는 알고리즘 중 하나가 에라토스테네스의 체 방식이다.
에라토스테네스의 체 알고리즘의 작동방식은 다음과 같다.
1. 2 ~ N까지의 범위가 담긴 배열을 만든다.
2. 해당 배열 내의 가장 작은 수 i 부터 시작하여, i의 배수들을 해당 배열에서 지워준다. (i는 소수이기 때문에 i자체는 지우지 않는다.)
3. 주어진 범위 내에서 i의 배수가 모두 지워지면 i 다음으로 작은 수의 배수를 같은 방식으로 배열에서 지워준다.
4. 더 이상 반복할 수 없을 때까지 2, 3번의 과정을 반복해준다.
에라토스테네스의 체 방식을 코드로 구현하면 다음과 같다.
def is_prime_num(n):
arr = [True] * (n + 1) # 특정 수가 지워졌는지 아닌지 확인하기 위한 배열
arr[0] = False
arr[1] = False
for i in range(2, n + 1):
if arr[i] == True: # 특정 수가 지워지지 않았다면 (소수여서)
j = 2
while (i * j) <= n:
arr[i*j] = False # i의 배수의 값을 False로 지워준다.
j += 1
return arr
arr = is_prime_num(50) # 0 ~ 50중 소수를 구하기 위한 함수
for i in range(len(arr)):
if arr[i] == True:
print(i, end=' ')
이 방식의 알고리즘은 거의 상수시간과 가까울 정도로 빠른 시간 내에 연산을 가능하게 해준다.
또한, 앞서 말한 약수의 특징을 이용해서 반복문의 횟수를 줄여주는 것이 가능하다.
즉, 범위 2 ~ N에서 N의 제곱근값보다 작은 부분들에 대한 처리가 끝나면, 제곱근값보다 큰 부분의 값 또한 처리가 된다는 말이다.
따라서 이를 코드로 작성하면 다음과 같다.
import math
def is_prime_num(n):
arr = [True] * (n + 1)
arr[0] = False
arr[1] = False
for i in range(2, int(math.sqrt(n)+1)):
if arr[i] == True:
j = 2
while (i * j) <= n:
arr[i*j] = False
j += 1
return arr
arr = is_prime_num(50)
for i in range(len(arr)):
if arr[i] == True:
print(i, end=' ')
소수판별 관련 문제
[백준] 1929번 소수 구하기 - seongonion.tistory.com/44
[백준] 4948번 베르트랑 공준 - seongonion.tistory.com/45
'알고리즘 > 이론' 카테고리의 다른 글
거듭제곱 더 더 더 빠르게 with 파이썬(Python) (2) | 2021.09.07 |
---|---|
투 포인터 알고리즘 (0) | 2021.02.01 |
퀵 정렬 알고리즘 with 파이썬 (Python) (0) | 2021.01.22 |
선택 정렬, 삽입 정렬 알고리즘 with 파이썬 (Python) (0) | 2021.01.22 |
재귀함수 - 파이썬(Python) (0) | 2021.01.13 |