9. 기타 알고리즘: 소수 판별, 에라토스테네스의 체 알고리즘
소수: 1보다 큰 자연수 중에서 1과 자신을 제외한 자연수로는 나누어 떨어지지 않는 수 이걸 코드로 그대로 옮기면 def is_prime_number(x): for i in range(2,x): if x%i==0: return False return True 이렇게 간단하게 쓸 수 있다 숫자가 X일 때 시간복잡도는 O(X)가 된다 여기서 약수의 성질을 이용하면 시간복잡도를 줄일 수 있다 모든 약수가 가운데 약수를 기준으로 곱셈 연산에 대해 대칭을 이룬다 예를 들어 16의 약수는 1, 2, 4, 8, 16인데, 1*16=16, 2*8=16으로, 4를 기준으로 대칭이다 따라서 특정한 자연수의 모든 약수를 찾을 때, 가운데 약수(제곱근)까지만 확인하면 된다 이것을 소수판별 알고리즘에 적용시키면 import m..
2022. 8. 14.