Reducing the Space Used by the Sieve of Eratosthenes When Factoring

Abstract

We present a version of the sieve of Eratosthenes that can factor all integers $\le x$ in $O(x\log \log x)$ arithmetic operations using at most $O(\sqrt{x}/\log \log x)$ bits of space. This is an improved space bound under the condition that the algorithm takes at most $O(x\log \log x)$ time. We also show our algorithm performs well in practice.

References in corpus (1)

• Computation of the least primitive root