I've wanted to write about factoring numbers in your head for a while, but never really had a good approach to analyze and discuss.

Recently, I've come across some strategies that mesh well with what I've discussed before on this site. Learning to factor a number in your head can be tricky, but it can be done.

BASICS: Starting from a given number between 1 and 10,000, you're only going to test for divisibility from the number 2, up to the square root of the given number. If you're familiar with estimating square roots, you only need the whole number part.

For example, if you're given the number 447, you only need to estimate the square root as 21, to realize you only need to be concerned with numbers from 2 to 21.

To narrow things down even further, you're only going to test for divisibility by prime numbers from 2 up to the limit you determine (21 in the above example). Between 2 and 100, there are only 25 prime numbers (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, and 97), so testing only for these minimizes the time it will take.

Certainly, divisibility tests for 2 (is the rightmost digit even?), 3 (do the digits add up to a multiple of 3?), and 5 (is the rightmost digit a 5 or a 0?) are well known, but how do you go about testing, and remembering the tests, for the higher primes?

TECHNIQUES: NUMBERS ENDING IN 9 - Back in April, I discussed how to work out divisibility tests for numbers ending in 9. For divisibility by 19, you would divide by 20, add up the quotient and remainder from that divisibility problem, and see if they added up to a multiple of 19. For 29, you'd run through the same process, but divide by 30, instead. For 59, you'd divide by 60, and so on.

When testing for various primes, however, working out all these quotients and remainders can quickly get confusing. Thankfully, it turns out that there's an alternative method, and it's even a little quicker!

Let's start with the test for 19. Instead of dividing by 20 and running through the process described above, split the number into the rightmost number and the rest of it, multiply that rightmost digit by 2, and add that total to the rest of the number. As an example, let's test 285 for divisibility by 19. You'd split 285 up into 28 and 5. Doubling the rightmost number, 5 × 2 = 10, so we'd add that 10 to the rest of the number, 28, to get 38. 38 is a multiple of 19, so 285 must be a multiple of 19! Wolfram|Alpha confirms that 285 is evenly divisible by 19.

For bigger numbers, you may not be sure about the result you got, so you simply run the test on your new total. For example, when testing 2,527 for divisibility by 19, you'd split it up into 252 and 7. Doubling the 7 makes 14, so you'd add 252 + 14 to get 266. Not sure whether 266 is evenly divisible by 19? We run the same test on 266, by splitting it up into 26 and 6. 6 doubled is 12, and 26 + 12 = 38, which we know is a multiple of 19! Therefore, 2,527 is a multiple of 19!

For 29 instead, you would divide up the number in the same way, but multiply the last digit by 3 instead, and then add . Why? Because 29 is right next to 30, and 30 divided by 10 equals 3 (similar to the way we used 2 as a test for 19, because 19 is next to 20). This same pattern holds for the other prime numbers ending in 9. For 59, you'd multiply the rightmost digit by 6 (59 + 1 = 60, 60 ÷ 10 = 6) and add it to the rest of the number. When testing divisibility by 79, you'd multiply the last digit by 8 before adding, and when testing divisibility by 89, you'd multiply the last digit by 9 before adding. Get the idea?

That's great for those numbers, but what about primes which don't end in 9?

SCALING NUMBERS TO END IN 9 - As also discussed in The Great Divide, you can also use this test on numbers which can be scaled up to end in 9.

This approach is particularly hand for primes ending in 3. For example, 13 × 3 = 39. Since 39 is right next to 40, you should quickly realize that you can test for divisibility by 13 by splitting the number as before, multiplying the rightmost number by 4 (40 ÷ 10 = 4), and adding that total to the rest of the number.

Is 507 evenly divisible by 13? 507 split becomes 50 and 7, multiplying 7 by 4 gives us 28, and 50 + 28 = 78. 78 is a multiple of 13, so 507 is evenly divisible by 13!

In the same way, 23 can be tested by multiplying the last digit by 7 and adding it to the rest of the number, because 23 can be scaled up to 69, and 69 is next to 70. Need to test for divisibly by 43, you split the number, multiply by 13 (do you see why?), and add as before.

Just using this approach covers 10 of the 25 prime numbers from 2 to 97. The well-known tests for 2, 3, and 5 add another 3, so you should comfortably be able to test for divisibility by more than half the prime numbers below 100!

Naturally, that brings up the question of how to handle the other half.

NUMBERS ENDING IN 1 - In my follow-up to The Great Divide, I cover a similar technique for numbers ending in 1. The big difference between the ending-in-9 technique and the ending-in-1 technique is that adding is replaced by subtracting.

Let's start by testing for divisibility by 11. The test will begin with the same splitting as before, and since 11 is next to 10, we'll multiply the last digit by 1. However, this time we'll subtract that number from the other numbers.

Is 341 evenly divisible by 11? We split 341 into 34 and 1, multiply 1 by 1, giving us 1, and subtract that from the rest of the number, 34 - 1 = 33, and since we know that 33 is evenly divisible by 11, then so is 341!

I'm sure you have the idea by now. For 31's divisibility test, you'd multiply the rightmost digit by 3 and subtract, for 41's test, you'd multiply by 4 and subtract, and so on.

SCALING NUMBERS TO END IN 1 - Just as before, this technique also applies to scaling numbers up to end in 1. For testing prime numbers ending in 7, including 7 itself, this is a big help.

The test for 7 begins by realizing that 7 can be scaled up to 21. This tells us that the rightmost number must be multiplied by 2 (remember why?) before subtracting from the rest from the rest of the number.

Is 665 evenly divisibly by 7? Let's use our knowledge of the 21 test to find out. The number is split into 66 and 5, and we double the 5 to get 10. 66 - 10 = 56, and we know 56 is a multiple of 7, so therefore 665 is evenly divisble by 7!

WIND-UP: At this point, we've covered the classic divisibility tests for 2, 3, and 5, as well as how to recall and perform easy divisibility tests for every prime number below 100 which ends in 1, 3, 7, and 9 - in other words, every test you need!

You'll need to recall that 9s and 3s require multiplying then adding, and 1s and 7s require multiplying followed by subtracting. When subtracting, note that you can always subtract the larger number from the smaller, which can prevent having to deal with negative numbers.

Since you're performing multiple tests, this won't be the quickest of mental math feats. However, being able to recall and perform tests for such a wide variety of prime numbers is still an impressive, and even useful, feat!