Something that comes up now and again in various contexts during lessons is how to tell whether a number is prime. My usual advice has been to use divisibility rules^{*}, and if none work, then it’s likely that the tested number is prime. Likely is not the same thing as certain, however, and, as the numbers get bigger, the divisibility rules will tend to be less and less helpful. For example, it’s easy to rule out that 51 is a composite number, i.e. not prime (and not ‘1’), but what about 1591? None of the common divisibility rules work, but that doesn’t mean 1591 is necessarily prime.

Knowing that there had to be some better way to determine whether a number is prime, I did a web search and found the following method: ^{†}

*To determine whether a number n is prime, square-root the number and let the result be r. Next, try to divide n by all the prime numbers that are less than r.*

Let’s see how this method works with a composite and a prime number, 539 and 113 respectively.