Faster enumeration of primesResearch Paper
Listing the primes below a bound is one of the oldest computational problems, and its cost is a standard benchmark for sieve algorithms. The sieve of Eratosthenes needs arithmetic operations on numbers of bits. On a multitape Turing machine, where the cost is the number of bit operations, the best known bound before this work was …