Sieve of Eratosthenes - Implementation

Implementation

In pseudocode:

Input: an integer n > 1 Let A be an array of Boolean values, indexed by integers 2 to n, initially all set to true. for i = 2, 3, 4, ..., √n : if A is true: for j = i2, i2+i, i2+2i, ..., n: A := false Now all i such that A is true are prime.

Large ranges may not fit entirely in memory. In these cases it is necessary to use a segmented sieve where only portions of the range are sieved at a time. For each round keep track of the smallest multiple of each prime seen. Storage will thus be bits where is the size of the segment.

For ranges with upper limit n so large that the sieving primes below √n, as required by the sieve of Eratosthenes, can't fit in memory, a slower but much more space-efficient sieve like that of Sorenson can be used instead.