10
$\begingroup$

I'm reading an algorithms book and I came across a code example for a primality test. The problem is that I couldn't understand the condition for the for-loop:

public static boolean isPrime( int N ) {
        if (N < 2) return false;
        for ( int i = 2; i * i < N; i++ ) {
            if ( N % i == 0 )
                return false;
        }

        return true;
}

If we multiply i by itself we would miss a lot of numbers to check. So if we want to check if n=10 is prime or not, then we would quickly end the loop by i=3. I know that the idea is finish the loop as early as possible, but how do we guarantee that by using that condition we are actually checking all possible divisors and the rest that we omitted are never going to be divisors?

This condition seems quite common and popular but I really wasn't able to understand it or find an interpretation. I understood the condition i < n/2 but not that one. I hope I'm not stupid!

$\endgroup$
1
  • 1
    $\begingroup$ I've edited your question to also include the loop body (or what I assume it must look like, anyway), since it seems relevant to the question. Please check that it approximately matches what your book has, and if not, correct it. Thanks! $\endgroup$ Apr 25 '15 at 15:21
19
$\begingroup$

If $n$ is not prime, then at least one of the factors of $n$ is at most as large as $\sqrt n$. To see why, let's suppose not. Since $n$ is not prime, $n = ab$ for some $a,b \neq 1$. If both $a$ and $b$ are larger than $\sqrt n$, then $a\cdot b > \sqrt n \cdot \sqrt n = n$. This clearly cannot be!

So you only need to check for factors up to $\sqrt n$.

$\endgroup$
5
  • $\begingroup$ Fair enough, but what is bothering me is that we are just checking $a=i, b=i$ in the for-loop. So it's only $a \cdot a$ (i*i < n) i.e we don't check for $2 \cdot 3$, $2 \cdot 4$ ... etc. Why is that? $\endgroup$
    – Jack Twain
    Apr 25 '15 at 11:47
  • 2
    $\begingroup$ @JackTwain you're confusing the condition in the loop with the body of the loop (which is omitted from the initial question and which should be checking whether $n/i$ is an integer). It's true that we can stop testing as soon as $i \cdot i \geq n$ (which is all you'd put at the top of the loop). $\endgroup$
    – hunter
    Apr 25 '15 at 12:09
  • 4
    $\begingroup$ @JackTwain it might help you to run the loop by hand for $n = 35$. $\endgroup$
    – hunter
    Apr 25 '15 at 12:10
  • $\begingroup$ Is the main idea that the condition i * i < n is equivalent to i < Math.sqrt(n)? $\endgroup$
    – Jack Twain
    Apr 26 '15 at 16:39
  • $\begingroup$ Yes, that's the idea $\endgroup$
    – davidlowryduda
    Apr 26 '15 at 17:02
4
$\begingroup$

Note that if $n$ is composite, then $n$ has a non-trivial factor $i$ such that $i \le \sqrt{n}$. Otherwise, any nontrivial factorization $n = ab$ would force $a, b > \sqrt{n}$, so that $n = ab > \sqrt{n}\times \sqrt{n} = n$, a contradiction.

$\endgroup$
2
$\begingroup$

The trial division test, abstractly formulated, is this: for each number $i$ in some suitable set, check whether $i$ divides $n$. If one such number is found, output "$n$ is composite", else output "$n$ is prime". (Perhaps you need to special-case $n=1$; I'll leave that to the reader).

Clearly no suitable set can contain $1$ or $n$, or we would report all numbers to be composite. No number is divisible by zero, and a number is divisible by $-x$ iff it is divisible by $x$, so we don't need to check numbers less than $1$. Also, if $m > n$ then $m$ does not divide $n$, so the set $\{2..n-1\}$ is definitely good enough: if we check all those numbers (and only those), then we are guaranteed to output the correct answer. It can be large, though, so we would like to thin it out if we can.

How do we guarantee that by using that condition we are actually checking all possible divisors and the rest that we omitted are never going to be divisors?

If $n / i$ is an integer, let's call it $k$, then definitely $n / k = n / (n/i) = i$ is also an integer. In other words, if $n = ik$ with $i < k$, then when you check for $i$ you indirectly also check for $k$: if $n$ can be factored into two non-trivial factors, finding the smaller of the two is finding at least one such factor (from which you can conclude that it's composite), and if $n$ can't be factored so, no such smaller-of-the-two factor will exist.

So, if instead of $\{2..n-1\}$ you only look at from 2 up to the largest of any possible smallest-factor-in-a-pair, you have still looked at enough possible candidates to be certain in your conclusion. Other people have already explained why $\sqrt{n}$ is the limit.

There is some subtlety in why $\lfloor\sqrt{n}\rfloor$, which is really what is being checked, is also good enough: either $\lfloor\sqrt{n}\rfloor = \lceil(\sqrt{n})\rceil = \sqrt{n}$ or $\lceil(\sqrt{n})\rceil^2 > n$, so either you have checked $\lceil(\sqrt{n})\rceil$ also, or you don't need to.

$\endgroup$
0
$\begingroup$

It may be worth mentioning that if $n$ is composite it has a prime factor less than or equal to $\sqrt{n}$. So in this 'trial division' algorithm, you only have to test $n$ for divisibility by primes up to $\sqrt{n}$.

$\endgroup$
2
  • $\begingroup$ However, if you're only interested in the primality of a single number $n$, it generally takes more effort to find all the primes up to $\sqrt n$ than to simply try all possible divisors, prime or not, up to $\sqrt n$. That said, one can easily optimize the example code to skip some obviously non-prime numbers (such as all multiples of 2, for a trivial x2 speed-up). And of course, if you want to do a lot of primality tests for similar-sized numbers, pre-compiling the list of possible prime divisors becomes more attractive. $\endgroup$ Apr 25 '15 at 15:42
  • $\begingroup$ ... In practice, I believe most efficient primality tests typically start with trial division by a precompiled list of small primes, and then (if the number passes the trial division test, and is larger than the square of the largest divisor tested) switch to more advanced algorithms like Miller-Rabin. $\endgroup$ Apr 25 '15 at 15:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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