As is well-known (and easy to prove), carrying out a sieve of Eratosthenes on the first $N$ integers takes a number of word operations in the order of $N \sum_{p\leq \sqrt{N}} 1/p \sim N \log \log N$, whether one uses it for finding the primes up to $N$ or for factoring the numbers up to $N$. It is also well-known that the number of bit operations required by the sieve of Eratosthenes to find the primes up to $N$ is $O(N \log N \log \log N)$, assuming, that is, that accessing a bit in an array of size $N$ takes time $O(\log N)$.

It seems to me that the number of bit operations required by the sieve of Eratosthenes to factor the integers from $1$ to $N$ is also $O(N \log N \log \log N)$ (unless one goes about things in a deliberately stupid way - doing the multiplication at the end by multiplying by your large primes before multiplying by your small primes, say; but nobody would do that).

(Here I am assuming something that was long suspected and recently proved, viz., that two $n$-bit numbers can be multiplied in time $O(n \log n)$ (Harvey-van der Hoeven).)

Am I right, or have I overlooked something? Is there a standard reference (or is this too obvious to be written down)?


1 Answer 1


Newer multiplication algorithms aren't needed to show such a time bound in this model.

Given a precomputed multiplication table of size $O(p)$, multiplication $a \times b$ of $a, b \leq p^{O(1)}$ takes a constant number of additions and table accesses. For example, let $p = \Theta(N^{1/3})$ then the pre-computation step takes $o(N)$ time and a multiplication takes $O(\log N)$ time.

The division is similar and can be assumed to take $O(\log N)$ time after a precomputation. Therefore, even using a naive repeated division like while x != 1: x := x / factor[x], it is possible to factor all integers up to $N$ in $O(N \log N \log \log N)$ time.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.