Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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.
