소수란, 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수를 말합니다. 어떤 자연수 n이 소수인지 판별하는 가장 기초적인 함수 코드는 아래와 같이 작성할 수 있습니다. def is_prime(n): for i in range(2, n): if n%i==0: return False ## 소수 아님 return True 2부터 n-1까지의 모든 수로 n을 나누어보는 방법입니다. 만약 나누어 떨어지는 수가 있다면 소수가 아닌게 되겠죠? 그럼 False를 리턴합니다. 그러나 이런 방법은 n까지의 모든 수를 확인해야 하기 때문에 시간복잡도는 ​O(n)​입니다. 따라서, n이 매우 크다면 비효율적이게 됩니다. ​ 좀 더 개선된 방법을 적용한 코드는 아래와 같이 작성할 수 있습니다. import math d..