the prime numbers below 30: 2 3 5 7 11 13 17 19 23 29 Algorithm and variants Pseudocode The sieve of Eratosthenes can be expressed in pseudocode, as follows: algorithm Sieve of Eratosthenes is input: an integer n > 1. output: all prime numbers from 2 through n. let A be an array of Boolean values, indexed by integers 2 to n, initially all set to true. for i = 2, 3, 4, ..., not exceeding do if A[i] is true for j = i2, i2+i, i2+2i, i2+3i, ..., not exceeding n do set A[j] := false return all i such that A[i] is true. This algorithm produces all primes not greater than . It includes a common optimization, which is to start enumerating the multiples of each prime from . The time complexity of this algorithm is , provided the array update is an operation, as is usually the case. Segmented sieve As Sorenson notes, the problem with the sieve of Eratosthenes is not the number of operations it performs but rather its memory requirements. For large , the range of primes may not fit in memory; worse, even for moderate , its cache use is highly suboptimal. The algorithm walks through the entire array , exhibiting almost no locality of reference. A solution to these problems is offered by segmented sieves, where only portions of the range are sieved at a time. These have been known since the 1970s, and work as follows: Divide the range 2 through into segments of some size . Find the primes in the first (i.e. the lowest) segment, using the regular sieve. For each of the following segments, in increasing order, with being the segment's topmost value, find the primes in it as follows: Set up a Boolean array of size . Mark as non-prime the positions in the array corresponding to the multiples of each prime found so far, by enumerating its multiples in steps of starting from the lowest multiple of between and . The remaining non-marked positions in the array correspond to the primes in the segment. It isn't necessary to mark any multiples of these primes, because all of these primes are larger than , as for , one has . If is chosen to be , the space complexity of the algorithm is , while the time complexity is the same as that of the regular