#math trivia for #June21: #173 is a prime. What’s the largest prime you need to try to divide it by to know this?
— Burt Kaliski Jr. (@modulomathy) June 22, 2012
An easy way to test whether a (small) number is prime is to see whether it’s divisible by any smaller primes. This is effectively how the classic Sieve of Eratosthenes works: given a sequence of numbers, as you discover a prime, you mark off the numbers that are divisible by the new prime. The highest number not yet marked off is the next prime.
If a number is divisible by a prime p that’s greater than its square root, however, then the number must also be divisible by a prime q that’s less than its square root. It’s sufficient therefore just to see whether the number is divisible by any primes less than or equal to its square root. For 173, the largest such prime is 13. You could do a primality test of 173 just by seeing whether it’s divisible by 2, 3, 5, 7, 11 or 13 — and it’s not divisible by any of them.
modulomathy.com 