소수(Prime Number) 판별은 프로그래밍에서 자주 등장하는 기본 알고리즘 문제입니다. 이 글에서는 파이썬으로 주어진 숫자가 소수인지 효율적으로 확인하는 방법을 소개합니다.
소수 판별의 핵심 원리
이 문제의 해결 원리는 다음과 같습니다. 주어진 숫자를 3부터 그 숫자의 제곱근까지의 모든 수로 나누어 보는 것입니다.
왜 제곱근까지만 확인하면 될까요? 어떤 수의 약수 중 가장 큰 것은 그 수 자신이고, 두 번째로 큰 약수는 최대 제곱근을 넘지 않기 때문입니다. 즉, 제곱근 이상의 범위에서는 나누어 떨어지는지 더 이상 검사할 필요가 없습니다. 이를 통해 불필요한 연산을 줄여 판별 속도를 크게 향상시킬 수 있습니다.
판별 함수의 동작 방식은 다음과 같습니다.
- 2보다 작은 숫자와 2로 나누어 떨어지는 숫자는
False를 반환합니다. - 그 외의 숫자는 제곱근까지의 어떤 수로도 나누어 떨어지지 않으면
True(소수), 하나라도 나누어 떨어지면False(소수 아님)를 반환합니다.
예제 코드
def is_prime(a):
if a < 2:
return False
elif a != 2 and a % 2 == 0:
return False
else:
return all(a % i for i in range(3, int(a**0.5) + 1))
num = int(input('enter a number'))
if is_prime(num) == True:
print("{} is a prime number".format(num))
else:
print("{} is not a prime number".format(num))코드 설명
- 2 미만 처리: 0과 1은 정의상 소수가 아니므로
False를 반환합니다. - 짝수 처리: 2 자체는 소수이지만, 2를 제외한 모든 짝수는 소수가 아니므로 바로
False를 반환해 검사를 생략합니다. - 제곱근까지 검사:
range(3, int(a**0.5) + 1)로 3부터 제곱근까지의 홀수 범위를 생성하고,all()함수를 사용해 모든 나눗셈 결과에 나머지가 있는지(즉, 한 번도 나누어 떨어지지 않는지) 확인합니다.
실행 결과
위 프로그램의 실행 예시는 다음과 같습니다.
enter a number24 24 is not a prime number enter a number47 47 is a prime number
24는 2로 나누어 떨어지므로 소수가 아니라고 출력되고, 47은 3부터 √47(약 6.85)까지의 어떤 수로도 나누어 떨어지지 않으므로 소수로 판별됩니다.
마무리
이처럼 제곱근까지만 검사하는 방식은 단순히 2부터 n-1까지 전부 나눠보는 방법보다 훨씬 효율적입니다. 특히 큰 숫자를 다룰 때 그 차이가 두드러지며, 파이썬의 all() 함수와 제너레이터 표현식을 활용하면 코드를 간결하게 유지할 수 있습니다.