Why does it take Osqrtn time to check if a number is primeSo

Why does it take O(sqrt(n)) time to check if a number is prime

Solution

If a number n is not a prime, it can be factored into two factors a and b

n = axb

If both a and b were greater than the square root of n, axb would be greater than n.

So at least one of those factors must be less or equal to the square root of n,

And

to check if n is prime, we only need to test for factors less than or equal to the square root.