May 19, 2022—Why square roots are used in trial division
At the end of Making Prime Numbers in Rust I explained how to make a prime number generator. It used trial division. You’ll notice that I don’t bother trying to divide the candidate number by any prime larger than its square root.
Why the square root?
Play with the top slider for a bit.
Do you get it yet?
Here’s a hint: once you’ve figured out that \(100 \div 2 = 50\), you then also know that \(100 \div 50 = 2\). There’s no need to also divide by 50 because you already know that answer.
The same goes for all these:
| 100 divided by | equals |
|---|---|
| 2 | 50 |
| 3 | 33.3 |
| 5 | 20 |
| 7 | 14.3 |
| 11 | 9.1 |
| 13 | 7.7 |
| 17 | 5.9 |
| 19 | 5.3 |
What do you notice about each of those pairs of numbers?
The square root is always at least as large as one of them.
Once you’ve divided by primes up through the square root then you already know the answers for all the primes larger than the square root. So there’s no need to also divide by those larger primes.