에라토스테네스의 체

[알고리즘][파이썬] 소수 판별 알고리즘(에라토스테네스의 체)

소수란? 2보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어떨어지지 않는 자연수를 말한다. 기본적인 소수 판별 방법 def is_prime(num): # 2부터 (num - 1)까지의 모든 수 확인. for i in range(2, num): # 하나라도 i로 나눠진다면 False를 반환. if num % i == 0: return False return True 이 때 시간복잡도는 O(n)이므로 n의 크기가 크면 비효율적이다. 이보다 좀 더 효율적인 방법은 n - 1까지가 아닌 n의 제곱근까지만 확인하는 것이다. 이렇게 해도 되는 이유는 무엇일까? 예를 들어 16의 약수 [1, 2, 4, 8, 16]이 있다고 해보자. 잘 살펴보면 가운데에 있는 수를 기준으로 대칭적으로 곱해 16을 만들..