에라토스테네스의 체소수(prime number)란?1과 자기 자신을 제외한 다른 어떤 수로도 나누어지지 않는 자연수이다. 예를 들어, 2, 3, 5, 7, 11 등은 소수이다. 일반적으로 소수를 판별하는 방법 중 하나는 특정 수가 소수인지 하나씩 확인하는 O(√N) 방식이다. 예를 들어, 어떤 수 xxx가 소수인지 판별하려면 1부터 xxx까지 모든 수를 나누어보는 대신, √x까지만 확인하면 충분하므로 O(√N)의 시간 복잡도를 갖는다.하지만 N까지의 모든 소수를 찾을 때 이 방식을 그대로 적용하면, 각 숫자마다 O(√N) 연산을 수행해야 하므로 전체적으로 O(N√N)의 시간 복잡도가 발생한다.이 때문에 여러 개의 소수를 한 번에 찾기에는 비효율적이며, 보다 빠르게 소수를 구하기 위해 에라토스테네스의 체 ..