[Note: n is a given integer (not the number of its digits)]
I'd like to know how O(sqrt(n)/log(n)) would compare against the computational complexity of the best available algorithms (as well as the other one available) for factoring.
Is it conceivable to think that since there are $\sqrt n/\log(\sqrt n) $ primes smaller than $\sqrt n$, in intuitive terms the above complexity could actually represent a lower limit that cannot be broken ? (This would correspond to the ideal situation where all primes were already available (precomputed) and readily accessible at no computational cost.)
After all the information about the divisibility for a given prime does not seem to suggest anything about the divisibility for any other one, and there seems to be no shared information. Or is this thought wrong ? If yes, which is, in intuitive terms clearly, a more plausible candidate for a (larger) lower bound for the factoring complexity?