Three Euler's Sieves and a Fast Prime Generator (Functional Pearl)
The Euler's Sieve refines the Sieve of Eratosthenes to compute prime numbers, by crossing off each non prime number just once. Euler's Sieve is considered hard to be faithfully and efficiently coded as a purely functional stream based program. We propose three Haskell programs implementing the Euler's Sieve, all based on the idea of generating just once each composite to be crossed off. Their faithfulness with respect to the Euler's Sieve is up to costly stream unions imposed by the sequential nature of streams.