World's most popular travel blog for travel bloggers.

# Running time of naive primality tester

, ,
Problem Detail:

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.