|
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. 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. To check 17 subtract it once to get 2730 and hence 273. Then add it to get 290 and hence 29. 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". For 23 add it to 2747 to get 2770 and 277, then substract 230 to get 47. 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. Similarly, 31 doesn't divide 353. 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. 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. |