On another note, it seems one can factorize in pseudopolynomial time by dynamic programming. Run the Sieve of Eratosthenes, but for each discovered prime, assign that prime to multiples of it that haven't been assigned to something else already. Then, starting at some number within the sieve, divide by the number assigned to it (which is one of its prime factors) and recurse until a prime is reached.
I don't know if this is common knowledge, though it seems simple in retrospect. It might be interesting as I didn't find any mention of it on the obvious web searches.