소수란 양의 약수를 딱 두 개만 갖는 자연수를 소수라 부른다. 2, 3, 5, 7, 11, …이 그런 수들인데, 소수를 판별하는 방법으로 첫번째 어떤 수 N 이 소수인지 판별하기 위해서는 N 을 2 부터 N 보다 1 작은 수까지 나누어서 나머지가 0 인 경우가 있는지 검사하는 방법과 두번째로 에라토스테네스의 체를 사용할 수 있다.
에라토스테네스의 체(Eratosthenes’ sieve)는, 임의의 자연수에 대하여, 그 자연수 이하의 소수(prime number)를 모두 찾아 주는 방법이다. 입자의 크기가 서로 다른 가루들을 섞어 체에 거르면 특정 크기 이하의 가루들은 다 아래로 떨어지고, 그 이상의 것들만 체 위에 남는 것처럼, 에라토스테네스의 체를 사용하면 특정 자연수 이하의 합성수는 다 지워지고 소수들만 남는 것이다. 방법은 간단하다. 만일 100 이하의 소수를 모두 찾고 싶다면, 1 부터 100 까지의 자연수를 모두 나열한 후, 먼저 소수도 합성수도 아닌 1을 지우고, 2외의 2의 배수들을 다 지우고, 3외의 3의 배수들을 다 지우고, 5외의 5의 배수들을 지우는 등의 이 과정을 의 100제곱근인 10이하의 소수들에 대해서만 반복하면, 이때 남은 수들이 구하고자 하는 소수들이다.
에라토스테네스의 체를 이용하여 50 까지의 소수를 구하는 순서를 그림으로 표현하면 다음과 같다.