Techniques for Factoring Numbers in Your Head
I factor numbers up to 3 or 4000 as my form of "counting sheep" when I want to relax and sleep. It's not hard. Obviously, you only need to check primes up to the square root of the number in question. 2, 3, 5 and 11 are easy to check. Beyond that, my main trick is to quickly reduce a divisibility check to a check on a smaller number. For example, if I want to know whether 2747 is divisible by 7, that's true if and only if 2040 is, which is divisible by 7 iff 204 is, which is divisible by 7 if 102 is, which is divisible by 7 iff 51 is, and it isn't. Alternatively, 2747 is divisible by 7 iff 2800-2747 = 53 is, which it isn't.<p>To check 13, I might subtract off 2600 to get 147, then also 130 to get 17. Or I might have started by adding 13 to get 2760 and hence 276, then subtracted 260 or 26.<p>To check 17 subtract it once to get 2730 and hence 273. Then add it to get 290 and hence 29.<p>To check 19 subtract 1900 to get 847, then 38 to get 805. Divide by 5 to get 161, add 19, and we've pretty much gotten to "no".<p>For 23 add it to 2747 to get 2770 and 277, then substract 230 to get 47.<p>2900 - 2747 = 153, which can only be divisible by 29 if it equals 29 x 7 (because else the last digit wouldn't be 3), which it doesn't.<p>Similarly, 31 doesn't divide 353.<p>2747 - 37 = 2710, and now there's a special trick, because 37 divides 111. 271 - 111 = 136. 136 - 37 = 99, which 37 obviously doesn't divide.<p>At 41 I'll just do a size check. 41 x 57 is too small, and 57 isn't prime anyway. 41 * 77 also couldn't work. So it's 41 x 67 or bust. That's 2400 + 280 + 60 + 7 ... and we have a winner! 2747 = 41 x 67. Checking the multiplication, (40+1) x (70-3) = 2800 + 70 - 120 - 3, which indeed works out to 2747.