A naive approach to checking if $n$ is prime is:
Prime(n):
for i=2, 3, ..., sqrt(n):
if i divides n then return "composite"
return "prime!"
I remember something about how measuring the complexity of this algorithm must be done in terms of the number of bits in $n$. In that case, I think that we also can't assume that checking whether $i$ divides $n$ can be done in $O(1)$ time.
So, I don't think this algorithm runs in $O(\sqrt n)$ time. What is its complexity?