이 글에서는 사용자로부터 입력받은 숫자가 1보다 클 때, 그 숫자가 소수(prime number)인지 아닌지를 판별하는 파이썬 프로그램을 작성해 보겠습니다.
소수란 무엇일까요?
소수란 1보다 큰 양의 정수 가운데 약수가 정확히 두 개, 즉 1과 자기 자신뿐인 수를 말합니다. 예를 들어 2, 3, 5, 7 등은 약수가 1과 자기 자신 두 개뿐이므로 모두 소수에 해당합니다.
소수 판별 파이썬 코드
# 입력받은 숫자가 소수인지 확인하는 파이썬 프로그램
# 사용자로부터 숫자 입력받기
num = int(input("숫자를 입력하세요: "))
# 주어진 숫자가 1보다 큰지 확인
if num > 1:
# 2부터 num/2까지 반복
for i in range(2, num//2 + 1):
# 나누어 떨어지는 수가 있는지 확인
if (num % i) == 0:
print(num, "은(는) 소수가 아닙니다")
print(i, "x", num//i, "=", num)
break
else:
# 2부터 num/2까지 나누어 떨어지는 수가 없으면 소수
print(num, "은(는) 소수입니다")
# 1 이하의 숫자 역시 소수가 아님
else:
print(num, "은(는) 소수가 아닙니다")
실행 결과
숫자를 입력하세요: 47 47 은(는) 소수입니다 >>> ================= RESTART: C:/Python/Python361/primeNum1.py ================= 숫자를 입력하세요: -2 -2 은(는) 소수가 아닙니다 >>> ================= RESTART: C:/Python/Python361/primeNum1.py ================= 숫자를 입력하세요: 3333 3333 은(는) 소수가 아닙니다 3 x 1111 = 3333
- 입력 1: num = 47 → 출력: 47은 소수입니다
- 입력 2: num = -2 → 출력: -2는 소수가 아닙니다
- 입력 3: num = 3333 → 출력: 3333은 소수가 아닙니다 (3 × 1111 = 3333)
프로그램 동작 원리
위 프로그램은 사용자가 입력한 숫자가 소수인지 여부를 검사합니다. 1 이하의 숫자는 정의상 소수가 될 수 없으므로, 입력값이 1보다 큰 경우만 판별 대상으로 삼습니다.
이후 2부터 입력값의 절반(num/2) 사이의 모든 수로 나누어 떨어지는지 확인합니다. 이 범위에서 약수를 하나라도 찾으면 그 숫자는 소수가 아니며, 끝까지 약수를 찾지 못하면 소수로 판정됩니다.
코드에서 for 문 바로 뒤에 붙은 else는 파이썬의 for-else 구문으로, 반복이 break 없이 끝까지 완료되었을 때만 실행됩니다. 덕분에 약수를 찾지 못한 경우에만 "소수입니다"라는 메시지가 정확히 한 번 출력됩니다.
성능 개선 팁
절반(num/2)까지만 검사해도 정확한 결과를 얻을 수 있지만, 더 효율적인 방법은 √num(제곱근)까지만 확인하는 것입니다. 약수는 항상 제곱근을 기준으로 짝을 이루기 때문에, 제곱근보다 큰 약수가 존재한다면 그에 대응하는 작은 약수도 반드시 함께 존재하기 때문입니다. 반복 범위를 range(2, int(num ** 0.5) + 1)로 줄이면 큰 수를 다룰 때 실행 속도를 크게 향상시킬 수 있습니다.