에라토스테네스의 체고대 그리스의 수학자인 에라토스테네스가 만들어 낸 소수를 찾는 방법마치 체로 치듯이 수를 걸러낸다고 하여 에라토스테네스의 체 라고 한다. 단일 숫자 여부를 확인 할 경우에는 특정한 숫자의 제곱근 까지만 약수의 여부를 검증하면 O(N^1/2)의 시간 복잡도로 빠르게 구할 수 있다.수가 수(N이라고 가정)를 나누면 몫이 생기는데, 몫과 나누는 수 둘 중 하나는 N 제곱근 이하이기 때문이다.만약, 대량의 소수를 한꺼번에 판별해야할 경우는 '에라토스테네스의 체'를 이용한다. 소수를 찾는 가장 간단하면서도 무식한 방법이다.예를 들어 1부터 100까지 소수를 찾을때 1을 제외한 나머지 수 중에서2를 소수로 분류하고 2의 배수를 다 지워준다.3을 소수로 분류하고 3의 배수를 다 지워준다.5를 소..