Prime Factorization using The Sieve of Eratosthenes

Question

I understand how the Sieve of Eratosthenes works for finding all primes less than a number n (start at 2 and cross out multiples and move on to next uncrossed out number and repeat etc.), but is there a way to factor an integer n using this algorithm?

Answer 1

First, you only need to get the primes up to $\sqrt{n}$ since any factorization of $n$ has a factor at most $\sqrt{n}$.

Second, to get the primes up to $m$, you only need to sieve by numbers up to $\sqrt{m}$ for a similar reason.

Therefore you only have to sieve with primes up to $\sqrt[4]{n}$ to get all the primes up to $\sqrt{n}$.

So this might be decent.

Answer 2

If you sieve up to $n$ and keep track of which primes cross out $n$ then you'll have found all the prime divisors of $n$. You will still have to check the multiplicities. For example, $12$ will be crossed out by both $2$ and $3$ but that doesn't tell you that $2^2$ is a factor.

The question is interesting but I suspect no answer would be really useful.