Why do we care whether a number is prime or not? Prime numbers are the atoms of mathematics. Understanding primes enables evil bankers to securely send your financial records to their other banking industry friends. They let Uncle Sam and the NSA keep its interest in world domination secret, you know, the one world order that is inevitable. Even Euclid knew that understanding primes was pertinent for human survival. He proved that there were an infinite number of primes around 300 B.C. I guess he had nothing better to do. They didn’t have YouTube back then.
Recall that a number is prime if it is only divisible by itself and 1.
The essence of the algorithm to determine if a number is prime is to divide the candidate number by 2, then 3, then 4… If you use a sieve (I’ll discuss more in a later post), you can avoid dividing by 4, 6, 8, 9 or any other number that can be ruled out as not being a prime because it is divisible by a smaller prime. For example, 4 is divisible by 2, so we don’t need to check 4 since we already checked 2.
Did you also know you only have to check up to the square root (inclusive) of your candidate as well. Why? Do you really want to know? You tell me… I’m waiting… OK. I’ll tell you. Look at 144. The square root of 144 is 12. If you check all numbers from 2-12 inclusive you are guaranteed to have checked all needed possibilities. But again, why? Why not check 13 if the candidate is 144?
If a number is not prime, it can be factored into two or more prime numbers (prime factors). In the case of two prime factors (our worst case scenario is two repeated primes), if both identical factors were greater than the the square root of the candidate, then the two identical prime factors multiplied together would be greater than the candidate – but this can’t be true. Hence, at least one of the factors must be less than or equal to the square root of the candidate. In the case of multiple prime factors, we would need to check for a number even less than the square root. As a result, the square root (inclusive of it) is the highest number we need to test.
Below is the Code in ‘C’ – The language handed to us by the God of programming, Dennis Ritchie.