When the largest known prime number was discovered recently, computers were used to verify that it was a prime.

While humans won't be working out whether numbers with millions of digits are prime in their head anytime soon, it is possible to quickly and easily test whether smaller numbers, such as those 1,000 and under, are prime. Learning how to do this in your head will also give you a better appreciation for the process used to find larger prime numbers.

BASICS: To be able to determine whether any give number from 2 to 1,000 is prime, you'll need to able to estimate the square root of anumber from 1 to 1,000, as taught here. When checking for primes, you can ignore the fractional part, and just focus on the whole number.

So, if you were a given a number such as 253, all you would really need to know for this feat is that the square root is above 15. This number will serve as the upper limit of the numbers you need to check. The lower limit, of course, is 2.

With our 253 example, does that mean we'll need to check whether 253 is divisible by every number from 2 to 15? No. In fact, we'll only need to check the prime numbers from 2 to 15 in this case: 2, 3, 5, 7, 11, and 13. Any of the remaining numbers above 2 can be made by multiplying 2 or more of those prime numbers, so checking the others is redundant.

So, your first step is to determine the square root, and then realize you'll need to check divisibility for all the prime numbers from 2 to the square root.

Another thing to remember that will speed up this feat is that we're not going to go through the full process to divide a given number by each of these prime numbers, but rather use simple tests to determine whether the given number is divisible by each number. For example, we don't need the answer to 253 ÷ 7, we just need a simple way to say whether 253 is evenly divisible by 7 or not.

We're not looking for an exact mathematical answer each time, just a series of yes-or-no answers up to a limit. If, at any time, we find that the given number is evenly divisible in one of our tests, we can stop there and definitively say that the number is NOT prime. If the given number isn't evenly divisible by any of our test numbers, we can definitively say that it IS prime.

CHECKING AT A GLANCE: The first 3 test can be done almost at a glance.

Is the rightmost digit a 0, 2, 4, 6, or 8? If so, it's not prime, unless the number is 2.

Is the rightmost digit a 5 or a 0? If so, it's not prime, unless the number is 5.

Just with a quick peek at the last digit, you can already tell whether it's divisible by 2 (the first test) or 5 (the second test). Testing for divisibility by 3 is also easy, as explained in the video below:



At this point, you might expect a test for divisibility by 7. I'm going to skip over the test for 7 now, but I will come back to it shortly. For now, we're going to test for divisibility by 11.

DIVISIBILITY TEST FOR 11: The divisibility test for 11 is surprisingly simple. You start by breaking the given number into two smaller numbers, one number consisting of only the rightmost digit, and the other number consisting of all the remaining numbers. Using our 253 example, we'd split into the numbers 25 and 3.

The next step is to treat those two numbers as a subtraction problem, and ask whether the result is evenly divisible by 11. If so, the original number is evenly divisible by 11.

Going back to 253, we work out that 25 - 3 = 22, which is evenly divisible by 11. Therefore, we know that 253 is also evenly divisible by 11, and therefore not prime.

DIVISIBILITY TEST FOR NUMBERS ENDING IN 1: With 1 minor alteration, this break-up-and-subtract approach can be expanded to cover almost any number ending in 1.

Let's take the next number ending in 1, 21, and show you how to test for its divisibility. For 21, take the lone leftmost digit, and multiply it by 2, then subtract. If the result is evenly divisible by 21, then the original number is evenly divisible by 21.

Even though we;ve already proved 253 isn't prime, let's try this test out on it anyway, to show you how it works. We break 253 into 25 and 3, then multiply 2 × 3 to get 6, then perform 25 - 6 to get 19. 19 isn't evenly divisibly by 21, so we know that 253 isn't evenly divisible by 21.

For 31, you'd muliply the lone digit by 3 before subtracting, for 41 you'd multiply the lone digit by 4 before subtracting, and so on. Effectively, removing the 1 shows you what number you'd multiply by for that number's divisibility test. Is a number divisible by 91? Multiply the lone number by 9 and subtract! Is a number evenly divisible by 121? Multiply the lone number by 12 and subtract! And so on.

This is an amazingly simple and useful pattern, and it can even be extended to numbers ending in odd digits without much difficulty.

DIVISIBILITY TEST FOR NUMBERS ENDING IN ODD DIGITS: You've probably already noticed that we're only testing for primes divisors, so we shoudln't need to test for divisibility for 21 itself, as 21 isn't a prime number. Since 21 is equal to 3 times 7, this same test can also be used to test for divisibility for 7. The steps are the same, except you ask whether the result is evenly divisibly by 7 instead of 21!

We've already determined that 253 isn't prime, so as a new example we'll test whether 347 is prime.

347 is bigger than 18² (324), but smaller than 19² (361), so we only need to test divisibility by the primes from 2 to 18.

Is 347 evenly divisible by 2? No, it's an odd number. Is 347 evenly divisible by 5? No, it doesn't end in a 5 or a 0. Is 347 evenly divisible by 3? 3 + 4 + 7 = 14, and 14 isn't evenly divisible by 3, so neither is 347.

Is 347 divisible by 11? 34 - 7 = 27, so 347 isn't evenly divisible by 11. Is 347 evenly divisible by 7? 34 - 2 × 7 = 34 - 14 = 20, and 20 isn't evenly divisible by 7, so 347 isn't evenly divisible by 7.

With just a few quick tests, we've already eliminated divisibility by 2, 3, 5, 7, and 11. We still need to test for divisibility by 13 and 17, so how do we do that?

Just as we used the test for 21 as a divisibility test for 7, we can use a similar approach to quickly find an appropriate divisibility test for other numbers ending in odd digits (except for 5, as we already have a simpler divisibility test for it).

Which multiply of 17 ends in 1? We have 17, 34, 51 - there we go! We can use the 51 test as a divisibility test for 17! Since it's 51, we have to break up the numbers as we did before, multiply the lone digit by 5, then do the subtraction, and ask if the result is evenly divisible by 17.

347 split becomes 34 and 7, just as before, but now we multiply that lone digit by 5 and subtract: 34 - 5 × 7 = 34 - 35 = -1. -1 isn't evenly divisibly by 17, so we've just established that 347 isn't evenly divisible by 17.

For 13, we have to go a bit farther: 13, 26, 39, 52, 65, 78, 91 - there it is! That means we have to multiply the lone digit by 9 before subtracting, and then ask whether the result is evenly divisible by 13.

For 347, this test becomes 34 - 9 × 7 = 34 - 63 = -29. That result, -29, isn't evenly divisible by 13, so 347 isn't evenly divisible by 13, either.

At this point, we've established that 347 isn't evenly divisibly by 2, 3, 5, 7, 11, 13, or 17, which are all the prime numbers in our established range of 2 to 18. This means we can say that 347 is indeed a prime number. Double checking with Wolfram|Alpha, we verify that 347 is a prime number.

With numbers up to 1,000, you'll also need divisibility tests for 19, 23, 29, and 31. We've already talked about 31, so that test is simple enough. 19 becomes 171, so you multiply the lone digit by 17 before subtracting. With 23, you use 161 (23 × 7), so the lone digit is multplied by 16, and with 29, you use the test for 261 (29 × 9), and therefore multiply the lone digit by 26 before subtracting. The BEATCALC website has a shortcut for multiplying by 26 which can be helpful.

FULL PROCESS: As a worst-case scenario, let's test the number 977. The square root is more than 31, but less than 32, so we'll need to test all the prime numbers from 2 to 31.

You should be able to tell at a glance that 977 is not evenly divisible by 2, 3, or 5.

Next, we move up to the break-up, multiply, and subtract tests. 97 - 7 = 90, so it's not evenly divisible by 11. We can also try 97 - 2 × 7 = 97 - 14 = 83 to establish it's not evenly divisibly by 7, and 97 - 3 × 7 = 97 - 21 = 76 to establish it's not evenly divisbly by 31.

97 - 5 × 7 = 97 - 35 = 62, which establishes it's not evenly divisible by 17. 97 - 9 × 7 = 97 - 63 = 34, and 34 isn't evenly divisibly by 13.

With a quick mental run-through, we've established 977 isn't evenly divisible by 2, 5, 3, 11, 7, 31, 17, and 13, in that order. It's an unusual order, until you get used to walking through that order.

The only remaining tests are the ones for 19, 23, and 29, which are the challenging ones. Remember, we use 16 to test for divisibility by 23, 17 to test for divisibility by 19, and 26 to test for divisibility by 29. This also means you should be comfortable mmultiplying any 1-digit number by 16, 17, and 26.

97 - 16 * 7 = 97 - 112 = -15, which isn't evenly divisibly by 23. 97 - 17 * 7 = 97 - 119 = -22, which isn't evenly divisible by 19. 97 - 26 * 7 = 97 - 182 = -85, which isn't evenly divisible by 29.

We've just run through every prime from 2 to 31, and found that 977 isn't evenly divisble by any of them. This means that 977 is prime, and Wolfram|Alpha verifies this for us.

SHORTCUTS: If you're worried about dealing with negative numbers, as often happens in the larger divisibility tests, you can simply do the multiplication needed, and then subtract the larger number from the smaller. For example, when testing 977 to see if it's evenly divisible by 29, you could think of the numbers as 97 and 26 * 7, working out the latter as 182, then performing 182 - 97 = 85. The sign doesn't matter in the divisibility tests, so you can always use this strategy.

If you're not comfortable working with the tests for 19, 23, and 29, you can avoid having to check for those by asking for a number from 1 to 350, instead of 1 to 1,000. That way, 17 is the largest divisibility test you'll need to perform.

NerdParadise.com has more on divisibility tests and testing for primes, if you wish to explore these patterns further.

Even if you don't perform this feat, I hope you read through it enough to understand each part of the process. That way, you'll have a better appreciation for the work required of computers when testing for extremely large primes.