[알고리즘] 에라토스테네스의 체 (Sieve of Eratosthenes), 소수 찾기 알고리즘

에라토스테네스의 체 (Sieve of Eratosthenes) 알고리즘은 소수를 찾기 위해서 사용하는 알고리즘입니다. 모든 수를 하나씩 확인하면, O(N)의 시간 복잡도가 소모되는 반면, 에라토스테네스의 체 방식을 이용하면, 1 ~ N이라고 하는 수까지 소수를 판별한다고 가정했을 때 O(N^(1/2))의 시간 복잡도로 문제를 해결할 수 있습니다. 그 이유는 어떤 수를 나누게 될 때 몫과 나누는 수가 있을 텐데, 두 수 중에서 하나는 반드시 N 제곱 근보다 작거나 같을 것이기 때문입니다. (ex 2 = 1 * 2, 4 = 2 * 2, 1 * 4와 같이 둘 중 하나는 원래 수의 제곱 근보다 작거나 같을 수밖에 없다.) 우리가 에라토스테네스의 체를 이용해 구하고자 하는 소수란 양의 약수를 두 개만 갖는 수를 의미하고, 이를 찾기 위해서 가장 작은 소수인 2부터 시작해서 소수의 배수들을 지워가는 방식을 N의 제곱 근까지 반복합니다. 이렇게 위의 과정을 진행한 후 지워지지 않은 수들을 소수라...

원문링크 : [알고리즘] 에라토스테네스의 체 (Sieve of Eratosthenes), 소수 찾기 알고리즘