le récit de ellie

소수란? 2보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어 떨어지지 않는 자연수 1. 2부터 n-1까지 모두 확인해보기 def is_prime_number(x): # 2부터 (x-1)까지의 모든 수를 확인 for i in range(2, x): # x가 해당 수로 나누어 떨어지면 if x % i == 0: return False # 나누어 떨어지는 경우가 없으면 return True 시간복잡도 : O(x) → x의 크기가 크면 비효율적 2. 2부터 제곱근까지만 확인해보기 예) 16의 약수 : [1, 2, 4, 8, 16] 해당 수를 살펴보면 가운데 수를 기준으로 대칭적으로 곱을 통해 16을 만들 수 있다. 이를 통해, 소수의 절반에 해당하는 제곱근까지만 살펴보면 소수 판별이 가능하다는 ..