알고리즘/이론
-
소수판별 알고리즘, 에라토스테네스의 체 - Python알고리즘/이론 2022. 12. 22. 00:52
1. 2부터 n전까지 나누어 나머지 0이 아니면 소수로 정의 - 시간복잡도 O(N) def is_prime_num(n): for i in range(2, n): if n % i == 0: return False # i로 나누어 떨어지면 소수가 아니므로 False 리턴 return True # False가 리턴되지 않고 for문을 빠져나왔다면 소수이므로 True 리턴 2. 약수의 특성을 활용한, √N까지 확인 - 시간복잡도 O(√N) 예시) 16의 약수들을 일렬로 나열하면 1, 2, 4, 8, 16이 된다. 중간값 4를 기준으로 양 옆의 약수들이 서로 대칭되어 있다. (1 * 16 = 16 * 1, 2 * 8 = 8 * 2) 따라서, 16의 약수를 찾고 싶다면 16의 약수의 중간값을 기준으로 한쪽만 검사를..