# Primality testing: Why is dividing a number $n$ by every integer between 2 and $\sqrt{n}$ an inefficient test?

In the paper "PRIMES is in P" the following is said (page 1):

Let PRIMES denote the set of all prime numbers. The definition of prime numbers already gives a way of determining if a number $n$ is in PRIMES: try dividing $n$ by every number $m \leq \sqrt{n}$ — if any m divides $n$ then it is composite, otherwise it is prime. This test was known since the time of the ancient Greeks — it is a specialization of the Sieve of Eratosthenes (ca. 240 BC) that generates all primes less then $n$. The test, however, is inefficient: it takes $\Omega (\sqrt{n})$ steps to determine if $n$ is prime. An efficient test should need only a polynomial (in the size of the input = $\lceil \log n \rceil$) number of steps.

Firstly, isn't complexity $\sqrt{n}$ already polynomial?

Secondly, why would complexity $\lceil \log n \rceil$ represent an efficient algorithm? This seems somewhat arbitrary to me.

• Try to understand the concept of pseudo-polynomial time. It will answer your question. – Mario Cervera Feb 21 '18 at 12:20
• In twenty seconds I can write down a number that this method won’t factor in a lifetime. – gnasher729 Feb 22 '18 at 18:58

The complexity is measured as a function of the size of the input.
You don't have here an array of $n$ numbers but a number $n$.
The size of the input is $O(\log n)$ (to store a number $n$ you need $\lfloor log_2(n) + 1 )\rfloor$ bits).
Hence, $O(\sqrt n)$ is not polynomial in the size of the input.

The answer to the second question is a direct consequence. Since the size of the input is logarithmic in $n$, an algorithm with logarithmic time complexity with respect to $n$ (and therefore, polynomial wrt the size of the input) would be efficient.

As an example, consider a number $M$ of size $n$, an algorithm with time complexity $O(log^k M)$ for a constant $k$, corresponds to a polynomial time algorithm (in the size of the input) of time complexity $O(n^k)$.

To see why $O(\sqrt{n})$ is not polynomial in the input length, consider what happens when you add a new digit to the right end of your input. This requires just one extra keystroke. So, the input length goes up by just one. However, note that the value of the input goes up by a factor of $10$. So, now you need to do $\sqrt{10}\approx 3$ times as many divisions to check if your input is prime or not. Increasing the input length by just one results in a $3$-fold increase in work. This is clearly exponential.
The $O(\sqrt{n})$ time algorithm is an example of a pseudo-polynomial time algorithm. These are algorithms whose running times are a polynomial in the numeric value of the input, but not necessarily in the length of the input. Another common example of a pseudo-polynomial time algorithm is the dynamic programming algorithm for $0-1$ knapsack.