While I know the time complexity for all known prime factorization algorithms is exponential, I can't seem to get this results for a very simple algorithm.
First assume we're doing this with numbers that are simply the product of two primes (the kind you get when working with RSA and others)...