[알고리즘] 에라토스테네스의 체

에라토스테네스의 체 소수를 찾을 때 가장 적은 시간 복잡도를 소요하는 알고리즘이다. 여러 개의 수가 소수인지 아닌지를 판별하며, N보다 작거나 같은 모든 소수를 찾을 때 사용할 수 있다. 에라토스테네스보다 시간 복잡도가 높은 알고리즘과 비교하여 해당 알고리즘의 이점을 파악한다. 일반적인 소수 찾기 알고리즘 소수의 판별법을 사용한다. 소수란 2보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어 떨어지지 않는 자연수이다. 6의 경우 1,2,3,5을 약수를 가지므로 소수가 아니고, 7의 경우 1,7만을 약수로 가지므로 소수라고 할 수 있다. 가장 간단한 소수 판별법은 아래와 같으며, 어떤 수의 소수를 찾을 때 시간 복잡도가 O(n)이 된다. # 가장 간단한 소수 판별법 # 모든 수를 나누어서 소..