Could some one please explain how to get the time complexity of checking if a number is prime? I'm really confused as to if it is $O(\sqrt{n})$ or $O(n^2)$.

I iterate from $i=2$ to $\sqrt{n}$ and continuously checking if n%i != 0.

However, do we consider the complexity of the square root function also?

If we do, the Newtons method for finding square roots has a complexity of $n^2$.

  • 5
    $\begingroup$ It depends what model of computation you're using and how you measure the length of the input. In some computation models, we assume we can add numbers of arbitrary size in constant time; in others, we assume that you have to add up the digits one by one (the same way you'd calculate 283746+384273). The other issue is that we normally write $n$ for the number of bits in the input. A $b$-bit number could have any value up to $2^b$ so the algorithm you describe is actually exponential in the number of bits (you check $\sqrt{2^b} = 2^{b/2}$ potential divisors). $\endgroup$ Oct 7, 2015 at 8:15
  • 8
    $\begingroup$ Your question is not about "the complexity of checking primality" but about the complexity of a specific algorithm for this task. Prime checking in general can be done in polynomial time with AKS. $\endgroup$ Oct 7, 2015 at 8:19
  • $\begingroup$ math.dartmouth.edu/~carlp/aks06-2015.pdf ​ ​ $\endgroup$
    – user12859
    Oct 7, 2015 at 9:53
  • 7
    $\begingroup$ You can avoid computing $\sqrt{n}$ (which doesn't have complexity $\Theta(n^2)$, but rather polylogarithmic in $n$) by checking whether $i^2 \leq n$. You can even avoid computing $i^2$ by updating it using the rule $(i+1)^2 = i^2 + 2i + 1$. $\endgroup$ Oct 7, 2015 at 20:40
  • $\begingroup$ @DavidRicherby does this mean counting has 2^b runtime ? $\endgroup$ Aug 30, 2016 at 20:57

2 Answers 2


When $n$ is the input, we test $\sqrt{n}$ divisors. However, we also have to take into account the complexity of division itself. For a number with $b$ bits, this takes $O(b \log b \log\log b)$ operations, when we are using the Schönhage–Strassen algorithm. Since half of the numbers below $\sqrt{n}$ have $\log(\sqrt{n})$ digits, we may assume the all have this amount of digits. It only matters a factor $\frac12$ at most, and that is absorbed in the $O$.

This gives a computational complexity of $O( \sqrt{n} \log \sqrt{n}\log(\log(\sqrt{n}) ) \log\log(\log(\sqrt{n}) )))$. We can simplify this to $O( \sqrt{n} \log(n) \log(\log(n) ) \log(\log(\log(n) )))$.

However, when notating it using the number of bits $b$ of a number, which is more standard usage, we get a computational complexity of $O(2^{b/2} b \log b \log\log b)$.

You also need to compute $\sqrt{n}$ but that has only complexity $O(b \log b \log\log b)$ when using Newton's method and the Schönhage-Strassen algorithm.

However, this is not optimal. The current best algorithm, the AKS algorithm, reaches a complexity of less than $O(b^{7})$ worst-case , which is much faster. (To be precise, even $O(b^{6+\varepsilon})$ for any $\varepsilon>0$ has been shown, but that is more complicated than it needs to be for this answer.)

  • 1
    $\begingroup$ The square root only needs to be calculated once, so the time is tiny compared to everything else. $\endgroup$
    – gnasher729
    Jul 6, 2016 at 22:57
  • 1
    $\begingroup$ Isn't it confusion to use bit notation for anything ? I mean counting from 1 to n is 2^b in bit notation. I have seen plenty of people thinking that integer factorization has exponential runtime, when counting has a worse exponential runtime using the same notation. $\endgroup$ Aug 30, 2016 at 20:52
  • $\begingroup$ @HopefullyHelpful It would depend on the numbers. If I check say 64 bit numbers that my computer can handle in a second even with a slowish algorithm, time dependent on n makes sense. If I do cryptography and check how long it takes to factor a 512 bit, 1024 bit, or 2048 bit number using the fastest algorithms known, then time depending on the input size is more useful. $\endgroup$
    – gnasher729
    Jun 22, 2022 at 16:48

A recent famous result is that checking if a number of $n$ bits is prime can be done in time polynomial in $n$, see the AKS test (it's somewhat heavy going).

  • 4
    $\begingroup$ This is mentioned in the other answer as well as in the comments to the question itself. $\endgroup$ Feb 14, 2016 at 23:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.