Improving on the Sieve of Eratosthenes

A paper by Helfgott published last week [1] gives a refined version of the sieve that takes less time and less space. His paper shows that it is possible to find all primes less than N in time

Furthermore, it is possible to factor all integers less than N in time

He also addresses finding all primes and factoring all integers in an interval [N – Δ, N + Δ] provided

In the case of such an interval, one can find all the primes in the interval in time O(Δ log N) and space O(Δ). And one can factor all integers in the interval in time and space O(Δ log N).

Source: www.johndcook.com