Lazy Wheel Sieves and Spirals of Primes

Abstract

The popular method of enumerating the primes is the Sieve of Eratosthenes . It can be programmed very neatly in a lazy functional language, but runs rather slowly. A little-known alternative method is the Wheel Sieve , originally formulated as a fast imperative algorithm for obtaining all primes up to a given limit, assuming destructive access to a bit-array. This article describes functional variants of the wheel sieve that enumerate all primes as a lazy list.