소수를 구하는 코드를 작성하기 전에, 먼저 소수(Prime Number)가 무엇인지 정확히 이해해야 합니다.
소수란 1과 자기 자신이라는 두 개의 약수만을 가지는 양의 정수를 말합니다. 예를 들어 2, 3, 5, 7처럼 1보다 큰 수 중에서 나누어 떨어지는 수가 자기 자신뿐인 수가 소수입니다. 참고로 1은 소수에 해당하지 않습니다.
그럼 지금부터 파이썬으로 소수를 찾는 세 가지 방법을 단계적으로 살펴보겠습니다. 각 방법은 이전 방법의 비효율을 개선하며 점점 더 최적화됩니다.
방법 1: 기본 for 루프 사용하기
가장 직관적인 방법입니다. 2부터 입력값까지 모든 수를 순회하면서, 각 수가 2부터 자기 자신 미만의 어떤 수로도 나누어 떨어지지 않으면 소수로 판단합니다.
def primemethod1(number):
# 결과를 저장할 리스트 초기화
my_primes = []
for pr in range(2, number):
isPrime = True
for i in range(2, pr):
if pr % i == 0:
isPrime = False
if isPrime:
my_primes.append(pr)
print(my_primes)
primemethod1(50)실행 결과
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
동작은 하지만, 약수를 이미 찾았음에도 불구하고 내부 루프가 끝까지 계속 실행된다는 비효율이 있습니다.
방법 2: break문으로 불필요한 반복 줄이기
약수를 하나라도 발견하면 더 이상 검사할 필요가 없습니다. break문을 추가하면 내부 루프를 즉시 탈출할 수 있어 성능이 향상됩니다.
def primemethod2(number):
# 결과를 저장할 리스트 초기화
my_primes = []
for pr in range(2, number + 1):
isPrime = True
for num in range(2, pr):
if pr % num == 0:
isPrime = False
break # 약수를 찾으면 즉시 반복 종료
if isPrime:
my_primes.append(pr)
return my_primes
print(primemethod2(50))실행 결과
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
방법 3: 제곱근까지만 검사하기
수학적으로 어떤 수 n이 소수가 아니라면, 반드시 √n 이하의 약수를 가집니다. 따라서 2부터 n-1까지 전부 검사할 필요 없이 √n까지만 확인하면 됩니다. 이렇게 하면 검사 범위가 크게 줄어들어 대량의 데이터를 처리할 때 특히 효율적입니다.
def primemethod3(number):
for pr in range(2, number):
isPrime = True
# 제곱근까지만 검사하여 연산량 대폭 감소
for num in range(2, int(pr ** 0.5) + 1):
if pr % num == 0:
isPrime = False
break
if isPrime:
print("Prime number:", pr)
primemethod3(50)실행 결과
Prime number: 2 Prime number: 3 Prime number: 5 Prime number: 7 Prime number: 11 Prime number: 13 Prime number: 17 Prime number: 19 Prime number: 23 Prime number: 29 Prime number: 31 Prime number: 37 Prime number: 41 Prime number: 43 Prime number: 47
정리 및 추가 팁
세 가지 방법을 비교하면 다음과 같습니다.
- 방법 1: 로직이 단순하지만 불필요한 반복이 많아 느립니다.
- 방법 2: break문으로 조기 탈출하여 속도를 개선합니다.
- 방법 3: 제곱근까지만 검사하여 가장 효율적입니다.
더 나은 성능이 필요하다면 에라토스테네스의 체(Sieve of Eratosthenes) 알고리즘을 고려해 볼 수 있습니다. 이 방식은 일정 범위 내의 모든 소수를 한 번에 구할 때 O(n log log n)의 시간 복잡도로 매우 빠르게 동작합니다. 또한 실무에서는 sympy 같은 라이브러리의 isprime() 함수를 활용하면 검증된 소수 판별 기능을 손쉽게 사용할 수 있습니다.