에라토스테네스의 체 소수는 암호학은 물론이고 수학과 컴퓨터 연산에서 중요한 역할을 담당한다. 소수(prime number)는 1보다 큰 정수로서 1과 자신으로만 나누어지는 수를 말한다. 소수의 개수를 세는 함수 𝜋(n)는 n보다 작거나 같은 소수의 개수를 구한다. 예를 들어 𝜋(25) = 9이다. 25보다 작거나 같은 소수가 2, 3, 5, 7, 11, 13, 17, 19, 23으로서, 총 9개이기 때문이다. 이 함수는 정수론(number theory)에서 핵심적인 역할을 담당한다.

소수를 세기 위해 factors.py(프로그램 1.3.9) 같은 프로그램을 사용할 수도 있다. 구체적으로는, 소인수를 출력하는 대신 주어진 숫자가 소수이면 True, 아니면 False라고 설정하도록 factors.py 프로그램을 수정하고, 카운터를 증가시키는 루프 안에 이 코드를 넣을 수 있다. n이 작으면 이 방법도 효율적이지만, n이 커지면 너무 느려진다.

[프로그램 1.4.3](primesieve.py)은 에라토스테네스의 체(sieve of Eratosthenes)로 알려진 기법을 이용해 𝜋(n)를 계산한다. 이 프로그램은 n개의 불형 요소를 가진 isPrime[] 배열을 이용해 n보다 작거나 같은 소수를 기록한다. i가 소수이면 isPrime[i]를 True로, 아니면 False로 설정하는 방법으로 소수를 찾아내는데, 먼저 배열 요소를 모두 True로 설정한 후, i를 2부터 시작해 n이 되기 전까지 다음의 과정을 반복한다.

• 다음번 숫자 중 인수를 찾지 못한 가장 작은 수(소수) i를 찾는다.

• isPrime[i]은 인수분해되지 않으므로 True로 놔둔다.

• i의 배수를 인덱스로 하는 isPrime[]의 모든 요소를 False로 설정한다.