Why is factoring large integers considered difficult?
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