The rule
prime if it has no divisor between 2 and √n
Why it works
A prime has exactly two divisors: one and itself. Testing only up to the square root is enough, because if a number had a divisor larger than its root, the matching partner would be smaller, and you would have found that one already.
How to do it by hand
- Numbers below 2 are not prime
- Test divisibility by 2, then by each odd number
- Stop at the square root of the number
- No divisor found means it is prime
What is worth knowing
The square-root cutoff is what makes the test practical: checking 1,000,003 needs only 1000 trials, not a million. Euclid proved there are infinitely many primes around 300 BC, with an argument short enough to fit in a sentence: multiply any finite list together, add one, and the result has a prime factor not on the list. Twin primes — pairs two apart, like 41 and 43 — are conjectured to be infinite too, and that remains open despite substantial progress since 2013. Primes thin out as numbers grow, but they never run out.