본문 바로가기

알고리즘

(1)

[알고리즘] 효율적인 소수 구하기, 에라토스테네스의 체 소수는 1과 자기 자신만을 약수로 가지는 수를 말한다. 즉 직관적으로 이를 코드로 표현한다면, for i in range(2, n): if n%i == 0: return False return True 단순히 2부터 n-1까지 순회하며 나눠지는 수가 있다면 소수가 아니라고 판단하면 된다. 하지만 이는 n까지 모두 순회하므로 O(n)의 시간복잡도를 가진다. 만약 n이 엄청 커진다면? 시간초과가 날 확률이 높다. 그렇다면 효율적인 소수를 구하려면 어떤 방식을 사용해야 할까? 우선 약수의 특성을 확인해야 한다. 예를 들어 16의 약수를 확인해보면, [1, 2, 4, 8, 16] 를 얻을 수 있다. 15의 약수는 [1, 3, 5, 15] 를 얻을 수 있다. 즉 가운데의 수를 기준으로 대칭적인 모습을 보이는데, ..

티스토리툴바