Complexity of finding factors of a number I have come up with two simple methods for finding all the factors of a number $n$. The first is trial division:


For every integer up to $\sqrt{n}$, try to divide by $d$, and if the remainder is $0$ then add $d$ and $n/d$ to the factor list. Assuming division and appending to a list are $O(1)$ operations for a CPU, this seems to be $O(\sqrt n)$. 


The second is to use trial division with prime factors:


Sieve all primes up to $\sqrt n$. The time complexity of the Sieve of Eratosthenes is $O(n \log \log n)$, so this is $O(\sqrt n \log \log \sqrt n)$?
From that list of primes, repeatedly try to divide by $p$ and move on to the next prime if the current prime will not divide evenly anymore. If it does divide, add $p$ and $n/p$ to the factor list. The density of primes is $n / \ln n$, and since primes go up to $\sqrt n$ the supposed time complexity is $O(\sqrt n / \ln \sqrt n)$. However, this does not take into account dividing by primes more than once.


I would like to know if my analysis is correct. It seems counter-intuitive that trial division only takes $O(\sqrt n)$ time, but $n$ is integer size, not input length. I don't think the time complexity of the second method is correct, but I am sure it must be faster than the first (trying primes instead of all numbers within a range).
The exact running time depends on your computation model. When analyzing arithmetic with large numbers, we usually count either bit operations, or arithmetic operations on words of size $O(\log n)$ (where $n$ is the input size, which in your case is the logarithm of the number you want to factor). This means that in a constant amount of time the first model only allows you to perform an operation involving a constant number of bits; and the second model allows you to perform a constant number of arithmetic operations (addition, subtraction, multiplication, division) on registers of length $C\log n$, where $C$ is some constant which you can use but must depend only on the algorithm.

In both models, the division operation itself won't take $O(1)$; indeed, the CPU cannot divide a large number $N$ by a prime $p$ in $O(1)$. So the running time is really $O(\sqrt{N}(\log N)^{O(1)})$ (where $N$ is the number you're trying to factor). We usually don't care about these logarithmic factors, so we use the notation $\tilde{O}(\sqrt{N})$, and we explain that it hides logarithmic factors.