Space-efficient version of sieve of Eratosthenes.
D. Eppstein, May 2004.
The main storage of the algorithm is a hash table D with sqrt(n)
nonempty entries for a total of O(sqrt n) space.
At any point in the algorithm, each prime p occupies a cell with key at
most 2n. E.g. by Bertrand's postulate, there is another prime p'
between n/p and 2n/p, and p' can not yet have been included because it(more...)