Why is factoring large integers considered difficult? I read somewhere that the most efficient algorithm found can compute the factors in $O(\exp((64/9 \cdot b)^{1/3} \cdot (\log b)^{2/3})$ time, but the code I wrote is $O(n)$ or possibly $O(n \log n)$ depending on how fast division and modulus are. I'm pretty sure I've misunderstood something somewhere, but I'm not sure where. Here's what I wrote in pseudo code form.

function factor(number) -&gt; list
    factors = new list
    if number &lt; 0
        factors.append(-1)
        number = -number
    i = 2
    while i &lt;= number
        while number % i == 0
            factors.append(i)
            number /= i
        i++
    return factors
You are confusing the number $n$ with the number of bits needed to represent $n$.  Here $b = $ the number of bits needed to represent $n$ (so $b \approx \lg n$).  This makes a huge difference.  A $O(n)$-time algorithm is a $O(2^b)$-time algorithm -- exponential in the number of bits.  In comparison, the "efficient" algorithm you found has a running time that is subexponential in $b$.

Example: Consider $n = 2,000,000$ (2 million).  Then $b=21$ bits are enough to represent the number $n$.  So, an algorithm that is $O(2^{b^{1/3}})$ will be much faster than an algorithm that is $O(2^b)$.  An $O(n)$ algorithm falls into the latter category, i.e., very slow.

See https://en.wikipedia.org/wiki/Integer_factorization