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?
Running time of naive primality tester
algorithms;complexity theory;time complexity
Firstly, you need to figure out what is the length of your input. Your input is $n$ so you need log(n) bits. Denote this number as $m$ not to get confused. Division takes either linear of m or constant time, depending on your model. So the question is how many time you gonna run it. Clearly, sqrt(n) times where $n=2^m$ so this algorithm runs in $O(2^{\frac{m}{2}})$ time. 