World's most popular travel blog for travel bloggers.

Running time of naive primality tester

, , No Comments
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?

Asked By : theQman
Answered By : Eugene

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.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback