Prime Factorization using The Sieve of Eratosthenes 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?
 A: 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.
A: 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.
A: The SOE is intended for finding primes. Finding factors using sieve-like algorithms would imply trying out every number a if it divides n then sieving all multiples of a.
A: I realize this is a late answer, but here is a modified sieve algorithm I devised to produce a list of the prime factors (along with corresponding multiplicities) of all natural numbers up to $N$ (though this is inefficient if you only want to factor $N$). For each number, I keep a mapping between each prime factor in its factorization and the corresponding multiplicity.
The algorithm is mostly the same as the original Sieve of Eratosthenes, except that for each prime number I come across (as can be checked by seeing that nothing is recorded for the current number's factorization), I keep a count $c$ to note which multiple of the prime I am currently processing. Then, for a given number $m$ that I "cross out" as not being prime, I note that the multiplicity of the current prime $p$ in the prime factorization of $m$ is simply one more than the multiplicity of $p$ in the factorization of $c$ (this works since if $m = cp$ and $c = kp^r$ for some natural number $k$ and multiplicity $r$, then $m = (kp^r)(p) = kp^{r+1}$). Note that $r$ has already been found by the sieve since $c < m$, and that if $p$ does not divide $c$, $r=0$ and the algorithm still works. I then increment $c$ and move on to the next multiple.
The familiar optimization of starting the crossing-off at $p^2$ for a prime $p$ doesn't seem to work here, since then $p$ won't be included in the factorization for all its multiples below $p^2$. 
