소수(素數, Prime Number)는 암호학을 비롯한 다양한 컴퓨터 과학 분야에서 핵심적인 역할을 담당합니다. 대표적으로 RSA와 같은 공개키 암호 알고리즘은 큰 소수의 곱을 기반으로 보안성을 확보합니다. 그렇기 때문에 Python 프로그램에서 주어진 수가 소수인지 아닌지를 판별하는 것은 여러 응용 프로그램에서 반드시 필요한 작업입니다. 소수란 1과 자기 자신 외에는 어떤 약수도 가지지 않는 수를 의미합니다. 이번 글에서는 주어진 숫자가 소수인지 확인하는 파이썬 코드를 단계별로 살펴보겠습니다.
기본 접근 방식
어떤 수가 소수인지 판단하기 위해 다음과 같은 절차를 사용합니다.
- 먼저 해당 수가 양수인지 확인합니다. 소수는 정의상 1보다 큰 양수만 가능하기 때문입니다.
- 2부터 입력값보다 하나 작은 수까지 범위 내의 모든 숫자로 나누어 봅니다.
- 이 범위 안에서 나누었을 때 나머지가 0이 되는 수가 하나라도 존재하면, 그 수는 소수가 아닙니다.
예제 코드
x = 23
if x > 1:
for n in range(2, x):
if (x % n) == 0:
print(x, "is not prime")
print(n, "times", x // n, "is", x)
break
else:
print(x, "is a prime number")
else:
print(x, "is not prime number")여기서 주목할 점은 for 문과 짝을 이루는 else 절입니다. 파이썬에서는 반복문이 break 없이 끝까지 실행되면 else 블록이 실행되는데, 이를 활용하면 약수를 찾지 못한 경우(즉, 소수인 경우)를 깔끔하게 처리할 수 있습니다.
실행 결과
위 코드를 실행하면 다음과 같은 결과를 얻습니다.
23 is a prime number
6i ± 1 형태를 활용한 최적화 방법
3보다 큰 모든 소수는 6i ± 1의 형태로 표현할 수 있다는 수학적 성질이 있습니다. 임의의 정수 i에 대해 6i, 6i+2, 6i+4는 2로 나누어 떨어지고, 6i+3은 3으로 나누어 떨어지므로 소수 후보는 6i−1과 6i+1뿐입니다. 아래 예제에서는 이 성질을 활용하여 5부터 시작해 i와 i+2만 검사함으로써 확인해야 할 수의 개수를 크게 줄입니다.
또한 검사 범위는 제곱근까지만 확인하면 충분합니다. n이 두 인수의 곱이라면 적어도 하나의 인수는 √n 이하이기 때문에, 그 이상은 검사할 필요가 없습니다. 덕분에 시간 복잡도가 처음 방법의 O(n)에서 O(√n)으로 크게 개선되어, 큰 수를 다룰 때 특히 유용합니다.
예제 코드
def CheckPrime(n):
# 2와 3에 대한 경우 처리
if (n <= 1):
return False
if (n <= 3):
return True
# 2 또는 3으로 나누어 떨어지면 소수가 아님
if (n % 2 == 0 or n % 3 == 0):
return False
# 6i ± 1 형태의 수만 검사
i = 5
while (i * i <= n):
if (n % i == 0 or n % (i + 2) == 0):
return False
i = i + 6
return True
# 입력값 확인
if (CheckPrime(31)):
print(" true")
else:
print(" false")
if (CheckPrime(25)):
print(" true")
else:
print(" false")실행 결과
위 코드를 실행하면 다음과 같은 결과를 얻습니다.
true false
31은 소수이므로 true, 25는 5×5로 나누어 떨어지므로 false가 출력됩니다. 실무에서는 이처럼 단순 나눗셈 방식 대신 6i ± 1 최적화 기법을 사용하면 연산량을 크게 줄일 수 있으며, 더 큰 수를 다룰 때는 밀러–라빈(Miller-Rabin) 같은 확률적 소수 판별 알고리즘을 고려할 수도 있습니다.