이번 튜토리얼에서는 주어진 숫자가 소수(prime number)인지 아닌지를 판별하는 다양한 방법을 살펴봅니다. 각 방법의 코드와 실행 결과를 함께 확인하며, 성능을 점차 개선해 나가는 과정을 이해해 보겠습니다.
방법 1: 기본적인 반복문 활용
가장 일반적이고 직관적인 소수 판별 방법입니다. 로직은 다음과 같습니다.
- 숫자가 1보다 작거나 같으면 False를 반환합니다.
- 2부터 n-1까지의 숫자 중 하나라도 나누어 떨어지면 False를 반환합니다.
- 반복문이 끝날 때까지 약수가 발견되지 않으면 True를 반환합니다.
예제 코드
# 소수 판별 함수
def is_prime(n):
if n <= 1:
return False
else:
for i in range(2, n):
# 약수 여부 검사
if n % i == 0:
return False
return True
print(f"Is 2 prime: {is_prime(2)}")
print(f"Is 4 prime: {is_prime(4)}")
print(f"Is 7 prime: {is_prime(7)}")실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
Is 2 prime: True Is 4 prime: False Is 7 prime: True
이 방법은 구현이 간단하지만, n-1까지 모든 숫자를 검사하기 때문에 숫자가 커질수록 시간이 오래 걸린다는 단점이 있습니다.
방법 2: 제곱근까지만 검사하기
수학적으로 어떤 수 n이 소수가 아니라면, 반드시 √n 이하의 약수를 가집니다. 따라서 n의 제곱근까지만 검사하면 반복 횟수를 크게 줄일 수 있습니다.
예제 코드
import math
# 소수 판별 함수
def is_prime(n):
if n <= 1:
return False
else:
# n의 제곱근까지만 반복
for i in range(2, int(math.sqrt(n)) + 1):
# 약수 여부 검사
if n % i == 0:
return False
return True
print(f"Is 2 prime: {is_prime(2)}")
print(f"Is 4 prime: {is_prime(4)}")
print(f"Is 7 prime: {is_prime(7)}")실행 결과
Is 2 prime: True Is 4 prime: False Is 7 prime: True
결과는 동일하지만, 검사 범위가 n에서 √n으로 줄어들어 큰 숫자를 판별할 때 훨씬 빠른 성능을 보여줍니다.
방법 3: 짝수 제외로 최적화하기
앞선 방법에서는 짝수도 함께 검사했습니다. 하지만 2를 제외한 모든 짝수는 소수가 될 수 없다는 사실은 누구나 알고 있습니다. 이 특성을 활용해 짝수를 미리 걸러내면 실행 시간을 더욱 단축할 수 있습니다.
예제 코드
import math
# 소수 판별 함수
def is_prime(n):
# 1 이하인 경우
if n <= 1:
return False
# 2인 경우
elif n == 2:
return True
# 2보다 큰 짝수인 경우
elif n > 2 and n % 2 == 0:
return False
else:
# 홀수만 검사하며 n의 제곱근까지 반복
for i in range(3, int(math.sqrt(n)) + 1, 2):
# 약수 여부 검사
if n % i == 0:
return False
return True
print(f"Is 2 prime: {is_prime(2)}")
print(f"Is 4 prime: {is_prime(4)}")
print(f"Is 7 prime: {is_prime(7)}")실행 결과
Is 2 prime: True Is 4 prime: False Is 7 prime: True
range 함수에 세 번째 인자로 2를 전달하여 3, 5, 7처럼 홀수만 검사합니다. 덕분에 반복 횟수가 절반으로 줄어들어 성능이 한층 더 향상됩니다.
마무리
지금까지 Python에서 소수를 판별하는 세 가지 방법을 알아보았습니다. 기본 반복문부터 시작해 제곱근 최적화, 짝수 제외 최적화까지 단계적으로 성능을 개선하는 과정을 통해 알고리즘 최적화의 기본기를 익힐 수 있었습니다. 실무에서는 상황에 맞는 방법을 선택하거나, 대량의 숫자를 처리해야 할 경우 에라토스테네스의 체(Sieve of Eratosthenes) 같은 고급 기법도 고려해 보세요.