# Sieve of Eratosthenes for factorization: bitwise complexity?

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)?

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.