제곱근을 이용한 소수 찾기 알고리즘
소수(Prime Number)는 1과 자기 자신만을 약수로 가지는 1보다 큰 자연수이다.
소수를 찾는 알고리즘은 수학적 계산의 핵심 요소 중 하나로, 효율성을 높이는 것이 중요하다.
이번 포스팅에서는 소수 찾기 문제에서 검사할 수의 제곱근을 사용하는 이유와,
이를 통해 시간 복잡도를 줄인 코드 구현에 대해 소개하려한다.
소수 판별의 기본 원리
소수를 판별하기 위해 가장 단순한 방법은 주어진 수 n에 대해
2부터 n-1까지의 모든 수로 나누어 나머지가 0이 되는지 확인하는 것이다.
하지만 이 방법은 매우 비효율적이며, 시간 복잡도는 O(n)이다.
제곱근을 활용한 소수 판별법
소수 판별에서 검사할 수의 제곱근을 사용하면
시간 복잡도를 O(√n)으로 줄일 수 있다.
이는 수학적 원리에서 비롯된다:
수학적 원리:
어떤 수 n이 소수가 아니라면, n은 두 개의 자연수 a와 b의 곱으로 표현될 수 있다.
이때 a와 b 중 하나는 반드시 √n 이하이다.
즉, a * b = n일 때, a <= √n이거나 b <= √n이 된다.
따라서 n이 소수가 아닌 경우, n의 제곱근 이하의 수 중에서 n을 나눌 수 있는 수가 반드시 존재한다.
이를 통해, √n 이하의 수까지만 확인하면 소수를 판별할 수 있다.
코드 적용 예시
다음은 제곱근을 사용하여 소수를 판별하고, 2부터 n까지의 소수 개수를 세는 코드이다:
import math
def isPrime(num):
if num < 2:
return False
for i in range(2, int(math.sqrt(num)+1):
if num % i == 0:
return False
return True
n = 100
cnt = 0
for num in range(2, n+1):
if isPrime(num):
cnt += 1
print("Number of Primes:", cnt)
> Number of Primes: 25
# 소수 리스트: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]시간 복잡도 분석
위 코드에서 'isPrime' 함수의 시간 복잡도는 O(√n)이다.
2부터 n까지 모든 수에 대해 'isPrime'을 호출하므로, 전체 시간 복잡도는 O(n√n)이 된다.
이는 모든 수에 대해 검사하는 일반적인 방식 O(n²)보다 훨씬 효율적이다.
결론
제곱근을 활용한 소수 판별법은 소수 찾기 문제에서 시간 복잡도를 크게 줄일 수 있는 방법이다.
이를 통해 범위 내의 소수를 효율적으로 찾을 수 있으며, 코드 경량화에 큰 효과를 얻을 수 있다.