#math trivia #173 solution

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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s