이 글에서는 파이썬을 이용해 주어진 숫자가 소수(prime number)인지 아닌지 판별하는 방법을 단계별로 살펴봅니다.
문제 정의
하나의 숫자가 주어졌을 때, 그 숫자가 소수인지 아닌지를 확인하는 것이 이번 문제의 목표입니다.
소수란 무엇인가?
1보다 큰 양의 정수 중에서 1과 자기 자신만을 약수로 가지는 수를 소수라고 합니다. 예를 들어 2, 3, 5, 7 등은 1과 자기 자신 외에 다른 약수를 가지지 않기 때문에 소수에 해당합니다.
반면 4는 1, 2, 4를 약수로 가지므로 소수가 아니며, 9 역시 3으로 나누어 떨어지므로 소수가 아닙니다.
판별 알고리즘의 핵심 아이디어
소수 판별 프로그램은 다음과 같은 논리로 동작합니다.
- 1 이하의 숫자는 소수가 될 수 없으므로, 숫자가 1보다 클 때만 검사를 진행합니다.
- 2부터 (num ÷ 2)까지의 범위에 있는 숫자들로 차례대로 나누어 봅니다.
- 이 범위 안에서 나누어 떨어지는 약수가 하나라도 발견되면 그 숫자는 소수가 아닙니다.
- 끝까지 검사했는데도 약수가 발견되지 않으면 그 숫자는 소수입니다.
예제 코드
num = 17
if num > 1:
for i in range(2, num // 2):
# num이 2와 n/2 사이의 어떤 수로도 나누어 떨어지지 않으면 소수
if (num % i) == 0:
print(num, "is not a prime number")
break
else:
print(num, "is a prime number")
else:
print(num, "is not a prime number")실행 결과
17 is a prime number
코드 상세 설명
위 코드에서 사용된 모든 변수는 지역 범위(local scope) 내에서 선언되며, 각 단계별 참조 관계는 다음과 같습니다.
num: 소수 여부를 판별할 대상 숫자입니다. 예제에서는 17을 사용했습니다.i: 반복문에서 2부터 num//2 - 1까지 차례대로 증가하며 나눗셈 검사에 사용되는 값입니다.num % i == 0: 나머지 연산자(%)를 활용해 num이 i로 나누어 떨어지는지 확인합니다.break: 약수를 찾는 즉시 반복문을 탈출하여 불필요한 연산을 줄입니다.for-else: 파이썬의 특수한 문법으로, 반복문이 break 없이 끝까지 실행된 경우에만 else 블록이 실행됩니다. 이를 통해 '약수를 못 찾았다'는 조건을 깔끔하게 표현할 수 있습니다.
성능 개선 팁
실제 프로젝트에서는 검사 범위를 √num(제곱근)까지만 줄여도 충분합니다. 약수는 항상 쌍으로 존재하기 때문에 √num 이하에서 약수가 없다면 그 이상에서도 약수가 없다는 것이 보장되기 때문입니다. 이렇게 하면 시간 복잡도를 O(n)에서 O(√n)으로 크게 개선할 수 있습니다.
결론
이번 글에서는 파이썬을 활용해 주어진 숫자가 소수인지 판별하는 프로그램의 작성 방법을 알아보았습니다. 나머지 연산자와 for-else 문법을 활용하면 소수 판별 로직을 매우 직관적으로 구현할 수 있으며, 검사 범위를 제곱근까지 줄이는 최적화 기법까지 익혀두면 더욱 효율적인 코드를 작성할 수 있습니다.