Benjamin asked me to do some factorization exercises.
I am not an expert in this field; I mainly use brute force, with some small tricks like the 1,001 method.
While researching mental factorization, I came across John Conway’s 150 method.
Using this technique, one can check a number for all prime factors under 40 with just one clever process.
Normally, when testing for primes, we do a modulo test for each divisor separately.
If it fails, we throw it away and start over for the next prime.
Conway’s idea eliminates that repetition:
You can reuse your previous work as you test several primes in one pass.
It’s surprisingly fast for 3- and 4-digit numbers — perfect for mental math.
Conway’s method of checking for primes below 40 is written down by Arthur Benjamin here:
The core idea
The trick is that the numbers 150\space -\space 156 collectively include almost all small primes:
150 = 2 \times 3 \times 5 \times 5
151 = \text{(prime, so skip)}
152 = 8 \times 19
153 = 9 \times 17
154 = 2 \times 7 \times 11
155 = 5 \times 31
156 = 12 \times 13
Since these consecutive numbers cover 2, 3, 5, 7, 11, 13, 17, 19,\space and \space 31, we checked all primes under 32, except 23 and 29.
Example 1: N = 931
The largest multiple of 150 below 931 is 150 \times 6 = 900.
Subtract it: A = 931 - 900 = 31.
Now count down by 6 (because K = 6):
31,\space 25,\space 19,\space 13,\space 7,\space 1,\space -5
Each step corresponds to 150 \space – \space 156 and the primes associated with it:
150, check for: 2, 3, 5
151, (prime; skip)
152, check for: 19
153, check for: 17
154, check for: 7, 11
155, check for: 31
156, check for: 13
Let’s do each step:
1: starting with 31. We check this for divisors 2,\space 3,\space \&\space 5. We find none.
2: Subtract 6 from 31 to get 25. We skip this, because 151 is prime.
3: Subtract 6 from 25 to get 19. We check this for divisor 19. We find that 19 is a divisor of 19.
4: Subtract 6 from 19 to get 13. We check this for divisor 17. We find none.
5: Subtract 6 from 13 to get 7. We check this for divisors 7 & 11. We find that 7 is a divisor of 7.
6: Subtract 6 from 7 to get 1. We check this for divisor 31. We find none.
7: Subtract 6 from 1 to get -5. We check this for divisor 13. We find none.
We now know that 7 and 19 are factors of 931.
Example 2: N = 689
Nearest lower multiple of 150: 150 \times 4 = 600.
Subtract: A = 689 - 600 = 89.
Now count down by 4:
89, 85, 81, 77, 73, 69, 65
At 65, we hit a multiple of 13 and indeed 689 \div 13 = 53.
Why it works
If N is your number and K the multiplier of 150 just below it, you are effectively checking:
N - 150K,
N - 150K - K
N - 150K - K - K
N - 150K - K - K - K
N - 150K - K - K - K - K
N - 150K - K - K - K - K - K
N - 150K - K - K - K - K - K - K
This is the same as:
N - 150K
N - 151K
N - 152K
N - 153K
N - 154K
N - 155K
N - 156K
Since divisibility doesn’t change when you add or subtract a multiple of a divisor, any “hit” in this sequence reveals a real factor of N.
Conway’s adaptation for checking factors 23 and 29