# Is the Time Complexity of Trial Division Exponential? [duplicate]

I know that there is already a similar question asked on here, but after reading the wiki page on trial division, I am confused, and the other answer doesn't help. The wiki page states that when doing trial division, "If a variant is used without primality testing, but simply dividing by every odd number less than the square root the base-2 n digit number a, prime or not, the algorithm can take up to about 2^(n/2) time".

Using such a variant, however, why wouldn't the time complexity be O(sqrt(n)) in the worst case? In the worst case you check all the numbers up to sqrt(n). So in the worst case, the algorithm would depend on the sqrt of the number of natural numbers before n, no? Also, would a variant that divides a number n by every natural number less than n until a factor is found in order to determine if n is prime is used be linear in time?

Link to the wiki I'm talking about: https://en.wikipedia.org/wiki/Trial_division (Quote pulled from the section titled, "Speed")

Side Question: Is this post better suited here as a new post, or should I have posted this question as a follow up to the other, similar question on trial division that was posted 4 years ago on here? I'm new here so I'm not sure what's preferred.

## marked as duplicate by David Richerby, Yuval Filmus time-complexity StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Jun 9 at 9:24

• @TaylorHuang Actually, it would still be linear time because you'd have to read the whole input to find out what $n$ is. – David Richerby Jun 9 at 8:25