이 게시글은 CS(컴퓨터공학) 프로그래밍 기초를 어느 정도 알고 있다고 가정하고 아주 간단하게 설명하는 게시글입니다.
혹시나 모르는 부분이 있으면 댓글로 질문해주세요.
한 줄 요약 : 말 그대로 해당 자연수가 소수인지 아닌지 판별해주는 알고리즘입니다. 실전에 유용한 소스 코드는 맨 아래에 있습니다.
소수(prime number)는 약수(factor)가 1과 자기 자신 뿐인 수를 의미합니다.
2, 3, 5, 7, 11, 13, ...이 소수입니다.
그러면 소수 판정을 할려면 어떻게 해야 할까요?
소수는 1과 자기 자신만 나누어지므로 다르게 말하면 1과 자기 자신 말고도 나누어지는 수가 있으면 소수가 아닌 합성수라는 뜻입니다.
예시로 6의 약수는 1, 2, 3, 6이며 1과 자기 자신(6) 말고도 2, 3으로도 나누어 떨어집니다.
즉, 2부터 시작하여 1씩 증가해서 단 1개라도 딱 나누어 떨어지면 소수가 아닌 것으로 판정할 수 있습니다.
그러나 2부터 시작하여 자기 자신 직전까지 진행해도 나누어 떨어지지 않으면 소수로 판정됩니다.
이것을 Python 소스 코드로 구현하면 다음과 같습니다.
import sys
input = sys.stdin.readline
# 버전 1 : O(N) 완전 탐색 버전 (2부터 N-1까지 일일이 나누기)
def is_prime(N:int) -> bool :
if N < 2 :
return False # 1 이하의 수는 소수가 아님
for i in range(2, N, 1) :
if N % i == 0 :
return False # 나누어떨어지면 소수가 아님
return True
print(is_prime(5)) # 결과 : True
print(is_prime(6)) # 결과 : False[5의 경우]
5 % 2 = 1
5 % 3 = 2
5 % 4 = 1
단 1개도 N % i == 0인 루프가 존재하지 않으므로 5는 소수로 판정됩니다.
[6의 경우]
6 % 2 = 0
6 % 3 = 0
6 % 4 = 2
6 % 5 = 1
1번째 루프에서 N % i == 0을 만족하므로 바로 False로 반환(return)합니다.
그러므로 6은 소수가 아닌 것으로 판정됩니다.
그런데 만약 N이 엄청 큰 수이면 시간이 오래 걸릴 것으로 보입니다.
예시로 N = 100000007라는 소수가 있다고 가정합니다.
import sys
import time
input = sys.stdin.readline
# 버전 1 : O(N) 완전 탐색 버전 (2부터 N-1까지 일일이 나누기)
def is_prime(N:int) -> bool:
if N < 2:
return False # 1 이하의 수는 소수가 아님
for i in range(2, N, 1):
if N % i == 0:
return False # 나누어떨어지면 소수가 아님
return True
# 100000000은 짝수라 의미가 없으므로, 1억 이상의 가장 작은 소수인 100000007을 넣습니다.
target_number:int = 100000007
# 시간 측정 시작
start_time = time.time()
result:bool = is_prime(target_number)
# 시간 측정 종료
end_time = time.time()
print(f"소수 여부 : {result}")
print(f"경과 시간 : {end_time - start_time:.6f} 초")이 소스 코드를 VS Code에서 직접 실행해보았습니다.
결과는 다음과 같이 나옵니다.
소수 여부는 True로 잘 나오고 경과 시간은 4.859729초가 나옵니다.
CS 분야 전공자라면 알겠지만 이 경과 시간이 나오면 상당히 오래 걸렸다는 것을 알 수 있습니다.
그러면 여기서 시간 복잡도 O(N)을 개선하는 방법이 있을까요?
자, 1부터 24까지 일일히 약수들을 다 구해봅니다.
[제곱근이 1.xxx인 경우]
1 -> 당연히 소수가 아님
2 -> 1 2 -> 소수 맞음
3 -> 1 3 -> 소수 맞음
[제곱근이 2.xxx인 경우]
4 -> 1 2 4 -> 소수 아님
5 -> 1 5 -> 소수 맞음
6 -> 1 2 3 6 -> 소수 아님
7 -> 1 7 -> 소수 맞음
8 -> 1 2 4 8 -> 소수 아님
[제곱근이 3.xxx인 경우]
9 -> 1 3 9 -> 소수 아님
10 -> 1 2 5 10 -> 소수 아님
11 -> 1 11 -> 소수 맞음
12 -> 1 2 3 4 6 12 -> 소수 아님
13 -> 1 13 -> 소수 맞음
14 -> 1 2 7 14 -> 소수 아님
15 -> 1 3 5 15 -> 소수 아님
[제곱근이 4.xxx인 경우]
16 -> 1 2 4 8 16 -> 소수 아님
17 -> 1 17 -> 소수 맞음
18 -> 1 2 3 6 9 18 -> 소수 아님
19 -> 1 19 -> 소수 맞음
20 -> 1 2 4 5 10 20 -> 소수 아님
21 -> 1 3 7 21 -> 소수 아님
22 -> 1 2 11 22 -> 소수 아님
23 -> 1 23 -> 소수 맞음
24 -> 1 2 3 4 6 8 12 24 -> 소수 아님
잘 보시면 같은 색상의 수끼리 서로 쌍대성을 이루는 것을 알 수 있습니다.
24의 경우를 예를 들어 보면
1 * 24 = 24
2 * 12 = 24
3 * 8 = 24
4 * 6 = 24
그러므로 1, 2, 3, 4만 탐색하면 나머지 6, 8, 12, 24는 굳이 탐색하지 않아도 되어서 중복 탐색을 피할 수 있습니다.
즉, 2부터 N의 제곱근 이하까지 탐색하면 시간복잡도가 O(√N) 수준까지 최적화가 됩니다.
단, 왜 N의 제곱근 미만이 아닌 이하까지 탐색해야 하냐면 25에서 만약 미만으로 정하면 5를 탐색하지 못 해 분명히 소수가 아닌데 소수로 판정되는 반례가 존재합니다.
그러므로 소수 판정할 때 2부터 N의 제곱근 이하까지 탐색해주세요.
이것을 소스 코드로 표현하면 다음과 같습니다.
import sys
input = sys.stdin.readline
# 버전 2 : O(√N) 최적화 버전 (제곱근까지만 나누기)
def is_prime(N:int) -> bool :
if N < 2 :
return False
# math.sqrt를 쓰지 않고 i * i <= N 조건을 활용하여 실수 오차 및 라이브러리 의존성을 제거합니다.
i:int = 2
# 2부터 N의 제곱근 이하까지 탐색합니다.
while i * i <= N :
if N % i == 0:
return False
i += 1
return True
print(is_prime(5)) # 결과 : True
print(is_prime(6)) # 결과 : False이번에는 동일하게 경과 시간을 측정하겠습니다.
우선 소스 코드를 작성합니다.
import sys
import time
input = sys.stdin.readline
# 버전 2 : O(√N) 최적화 버전 (제곱근까지만 나누기)
def is_prime(N:int) -> bool :
if N < 2 :
return False
# math.sqrt를 쓰지 않고 i * i <= N 조건을 활용하여 실수 오차 및 라이브러리 의존성을 제거합니다.
i:int = 2
# 2부터 N의 제곱근 이하까지 탐색합니다.
while i * i <= N :
if N % i == 0:
return False
i += 1
return True
# 100000000은 짝수라 의미가 없으므로, 1억 이상의 가장 작은 소수인 100000007을 넣습니다.
target_number:int = 100000007
# 시간 측정 시작
start_time = time.time()
result:bool = is_prime(target_number)
# 시간 측정 종료
end_time = time.time()
print(f"소수 여부 : {result}")
print(f"경과 시간 : {end_time - start_time:.6f} 초")VS Code에서 직접 실행하여 결과를 확인하겠습니다.
와우! 이 정도면 엄청난 최적화입니다!
약 3,107배 정도 더 빨라졌습니다!
시간 복잡도 O(N)과 O(√N)의 차이가 이렇게 큽니다.
참고로 실전에서 유용한 소수 판정은 기존 소스 코드에서 6k - 1, 6k + 1만 탐색하는 6-wheel 수학적 기법을 함께 적용하는 것입니다.
# 버전 3 : 소수는 6k-1, 6k+1 형식으로만 이루어져 있다는 수학적 기법을 추가합니다.
# 이러면 탐색 범위가 버전 2의 1/3 수준으로 떨어져 더 최적화가 됩니다.
# 소수 판정 알고리즘 사용할 때 이 소스 코드를 사용해주세요.
def is_prime(N:int) -> bool:
if N < 2:
return False
if N == 2 or N == 3:
return True # 2와 3은 소수
if N % 2 == 0 or N % 3 == 0:
return False # 2나 3의 배수는 모두 제외
# 5부터 시작해서 6씩 건너뜁니다. (i는 6k-1, i+2는 6k+1에 대응)
i:int = 5
while i * i <= N :
if N % i == 0 or N % (i + 2) == 0:
return False
i += 6
return True예시로 997을 버전 2으로 탐색할려면 997의 제곱근이 약 31.575이므로
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31
총 30번 루프를 돌아야 합니다.
물론 이것도 충분히 빠른 편이나 버전 3을 적용하면 다음과 같은 수만 루프를 돌면 됩니다.
5, 7, 11, 13, 17, 19, 23, 25, 29, 31
이렇게 루프 횟수가 1/3 수준으로 떨어졌습니다.
import sys
import time
input = sys.stdin.readline
# 버전 3 : 소수는 6k-1, 6k+1 형식으로만 이루어져 있다는 수학적 기법을 추가합니다.
# 이러면 탐색 범위가 버전 2의 1/3 수준으로 떨어져 더 최적화가 됩니다.
# 소수 판정 알고리즘 사용할 때 이 소스 코드를 사용해주세요.
def is_prime(N:int) -> bool:
if N < 2:
return False
if N == 2 or N == 3:
return True # 2와 3은 소수
if N % 2 == 0 or N % 3 == 0:
return False # 2나 3의 배수는 모두 제외
# 5부터 시작해서 6씩 건너뜁니다. (i는 6k-1, i+2는 6k+1에 대응)
i:int = 5
while i * i <= N :
if N % i == 0 or N % (i + 2) == 0:
return False
i += 6
return True
# 100000000은 짝수라 의미가 없으므로, 1억 이상의 가장 작은 소수인 100000007을 넣습니다.
target_number:int = 100000007
# 시간 측정 시작
start_time = time.time()
result:bool = is_prime(target_number)
# 시간 측정 종료
end_time = time.time()
print(f"소수 여부 : {result}")
print(f"경과 시간 : {end_time - start_time:.6f} 초")이 소스 코드를 실행하여 경과 시간을 측정합니다.
와우! 정말 놀라울 정도로 66% 이상으로 감소되었습니다.
이렇게 해서 실전에서는
# 소수 판정 알고리즘
def is_prime(N:int) -> bool :
if N < 2:
return False
if N == 2 or N == 3:
return True # 2와 3은 소수
if N % 2 == 0 or N % 3 == 0:
return False # 2나 3의 배수는 모두 제외
# 5부터 시작해서 6씩 건너뜁니다. (i는 6k-1, i+2는 6k+1에 대응)
i:int = 5
while i * i <= N :
if N % i == 0 or N % (i + 2) == 0:
return False
i += 6
return True이것을 사용해주세요.
'초간단 알고리즘 설명' 카테고리의 다른 글
| [알고리즘 설명][Python] 유클리드 호제법(euclidean algorithm) (0) | 2026.06.15 |
|---|---|
| [알고리즘 설명][Python] 해싱(hashing) (0) | 2026.06.14 |
| [알고리즘 설명][Python] 브루트 포스 알고리즘(brute force) (0) | 2026.06.12 |
| [알고리즘 설명][Python] 피타고라스 정리(pythagoras' theorem) (0) | 2026.06.10 |
| [알고리즘 설명] 알고리즘 구현에 필요한 간단한 Python 기초 문법 모음 (0) | 2026.06.09 |