An efficient way to eliminate possible (prime) factors in your head is
to add and subtract multiples of the possible factor to the number to
be factored so as to make a multiple of 10, then divide the number by
10. The resulting number will be divisible by the possible factor
(unless the possible factor contains 2 or 5) iff the original number
was.
How do you know what to multiply your possible factor by?
If your possible factor ends with 1 or 9, then:
- if your putative composite ends in 1 or 9, multiply by 1;
- if it ends in 2 or 8, multiply by 2;
- if it ends in 3 or 7, multiply by 3;
- if it ends in 4 or 6, multiply by 4;
- if it ends in 5, multiply by 5.
>>> lastdigits = Numeric.multiply.outer([1, 3, 7, 9], Numeric.arange(10)) % 10
>>> complements = 10 - lastdigits
>>> Numeric.minimum(lastdigits, complements)
array([[0, 1, 2, 3, 4, 5, 4, 3, 2, 1],
[0, 3, 4, 1, 2, 5, 2, 1, 4, 3],
[0, 3, 4, 1, 2, 5, 2, 1, 4, 3],
[0, 1, 2, 3, 4, 5, 4, 3, 2, 1]])
So if your possible factor ends with 3 or 7, then:
- if your putative composite ends in 1 or 9, multiply by 3;
- if composite ends in 2 or 8, multiply by 4.
- if composite ends in 3 or 7, multiply by 1;
- if composite ends in 4 or 6, multiply by 2;
- if composite ends in 5, multiply by 5.
So you really only need to remember the sequence 3 4 1 2 5 for 3 or 7.
So to factor 3829:
- it's not divisible by 2 or 5 obviously;
- the digit sum is 4, so it's not divisible by 3;
- adding 21 (3*7) gives 3850, which is 10*385; subtracting 35 (5*7)
gives 350, which is 10*5*7. So it's divisible by 7, so you can do
the long division to figure out what's left: 547.
- No need to test 547 for divisibility by 2, 3, or 5.
- It's not divisible by 7 because it's 54*10+7, and 54 isn't divisible by 7.
- 5+7-4 is 8, which is not congruent to 11, so it's not divisible by 11.
- 547+13 is 560, or 10*56, and 56 isn't divisible by 13.
- 547-17 is 530, or 10*53, and 53 isn't divisible by 17. (53+17=60.)
- 19*3 = 57; 547-57 = 490, which isn't divisible by 19.
- 547+23 = 570, which isn't divisible by 23.
- 29*3 = 87; 547-87 = 460, which isn't divisible by 29.
- 29*29 > 547. So 547 is prime.
A fellow named Ping taught me this, but I don't remember his name.
