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

Question

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.

Answer 1

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)$.

Answer 2

newbie's answer already explains it all. But if I had to add something to this, I'd put it in simpler words.

When you talk about a polynomial time algorithm, what you actually mean is that the running time of the algorithm is a polynomial in the input length. The input length is, roughly speaking, the number of keystrokes required to express the input.

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.

Answer 3

First of, you don't need to test the even numbers.

Second of, you don't need to test the numbers which end with a zero or with a 5.

Third of, you don't need to test any numbers which are not in the primorial base 30 a multiple of $30-+ (1,7,11,13)$

Fourth of you don't need to test any numbers which are not in the primorial base 210 a multiple of $210-+ (1,11,13,17,19,23...)$

Fifth of... Repeat.

Answer 4

So what is the issue here? The algorithm clearly requires (sqrt(n)//2) divisions by the respect to the N. So if I measure complexity by the function: input number -> #of divisions, then I will get theta(sqrt(n)) complexity.

I believe the actual problem why this algorithm is inefficient that division is not a basic operation, and that the division's complexity is based on the length of divided numbers. Which I didn't see mentioned in any of the responses.

Also there seems to be a misunderstanding in expression of the complexity in "O" notation - O(sqrt(n)) is a subset of O(n) and therefore the algorithms should be more efficient, because power of 0.5 will be less than power of 1 for all positive integers. The other thing is that all algorithms with this (sqrt) complexity can be implemented only in such a way you showed - why is that inefficient. But I state that O(sqrt(x)) <= O (x).