소수 판별 알고리즘
기본적인 소수를 판별하는 알고리즘은 다음과 같다.
def is_prime_easy_version(target):
for i in range(2, target):
if target % i == 0:
return False
return True즉, target value를 제외한 그 전의 값들을 모두 target value와 나누어서 나누어 떨어지는 값이 있으면 그 target value는 소수가 아닌 것이다.
하지만 이 방식은 N값의 소수를 구하려고 할때, 최대 O(N)의 시간 복잡도를 갖는다.
따라서 이 시간 복잡도를 낮추기 위해 조금 다른 방법을 생각해봐야한다.
첫 번째로 생각한 것은 2부터 target value를 2로 나눈 몫까지로 target value를 나누고 만약 그 중에서 나누어 떨어지는 수가 있다면, 이 방식으로도 소수를 구할 수 있다.
def is_prime_improved_version(target):
for i in range(2, int(target / 2)):
if target % i == 0:
return False
return True그러면 이 방법은 최대 O(N/2)의 시간 복잡도를 갖는다.
그런데 생각해보면 8을 예로 들어보자. 8은 2 * 4와 4 *2로 나눌 수 있는데, 이 식은 사실상 같다.
즉, 8이 소수가 아니라는 것을 증명하려면 2라는 값 하나만 가지고 있다는 것을 증명하면 되는 것이다!
그리고 8의 제곱근은 2.8284271247461903이라는 값을 가진다.
결론적으로 target value의 제곱근까지의 값 중에서 target value를 나눌 수 있는 수가 존재한다면 target value는 소수가 아니게 되는 것이다. 그리고 이 방법은 시간복잡도 O(N^1/2)를 가진다.
따라서 소수를 판별하는 알고리즘 중 최적해는 다음과 같이 제곱근을 이용하면 되는 것이다.
def is_prime_sqrt_version(target):
for i in range(2, int(math.sqrt(target)) + 1):
if target % i == 0:
return False
return True
에라토스테네스의 체
그럼 이제 에라토스테네스의 체라는 것을 알아보자.
여기서 '체'는 말그대로 '거른다'는 의미이다.
즉, 에라토스테네의 체는 쉽게 말해서 다음과 같은 개념이다.
1부터 100까지의 숫자가 있는데, 이 중에서 소수를 찾는 알고리즘이다.
그리고 원리의 개념은 다음과 같다.
1부터 100까지의 숫자가 있으면, 2부터 출발하여 자기 자신을 제외한 배수의 값을 제외한다. 그리고 이를 모두 수행해서 남은 수들이 소수가 된다. 하나하나 차근차근 이해하고 보니 아주 쉬운 개념이다. 그럼 이를 한번 적용해보자.
def sieve_of_eratosthenes(target):
check_list = [True] * (target + 1)
for i in range(2, math.sqrt(target) + 1):
if not check_list[i]:
continue
for j in range(i + i, target + 1, i):
check_list[j] = False
for i in range(2, target + 1):
if check_list[i]:
print(i, end=' ')
물론 파이썬의 primePy 모듈을 사용해서 구해도 된다. 사용법은 다음 링크를 참고하자.✌️
[python] 소수(prime number) 구하기, primePy 모듈 활용
소수(prime number)란 1과 자기 자신으로만 나누어 떨어지는 숫자들을 의미합니다. 예를 들어, 2, 3, 5, 7, 11, 13... 등이 소수에 해당합니다. 물론 for 문과 if 문을 잘 활용한다면 소수를 구하는 함수를
bskyvision.com
