How Prime Numbers Work

Frank: “Hey folks. My it is a scorcher out today at 39* F. If you are sitting in your basement waiting for that tornado to pass then this is for you. If you’re not, then I give you permission to listen in too. I am Frank the Freak. I once tried to work as a host for a TV channel but they wouldn’t let me so I started working here. I have, sitting here with me, a professor in number theory who has a Ph.D. in applied mathematics. Today, he will demonstrate his highly efficient prime seeker algorithm. Well, I’m sitting here having fun talking, wasting your time, so let’s get to business. Our first caller is Bob from the other room. Bob, you there?”

The Basics

Bob: “Hi, Frank? What is a prime number anyhow?”
Frank: “Good question Bob, let's see if the professor can answer it.”
Professor: “Well Frank, a prime number is a number into which no other numbers go, except one and that number that we are testing.”
Frank: “Umm, could you be a bit more specific for our audience? I think we need some more detail.”
Professor: “Certainly Frank. Now what I mean by that is.. well, let’s give a couple examples, like 12 and 13. To see if 12 is prime or not we check to see if there are any numbers that go into it starting with one. Does 1 go into 12? Yes, however as stated earlier you can’t tell if a number is prime just by looking at the first number on the number line. So let's look at the next one which happens to be 2. Does 2 go into 12? Again yes but this time 2 is not 1 or 12, so 12 must be composite or, any nonprime number. For the sake of demonstration we will go on with testing the number 12 which we already know is not prime. Next on the list is 3. Does 3 go into 12? Yes again, so if 2 did not cut it we have 3 to back it up. Does 4 go into 12?”
Frank: “Jeez is this a perfect number or something? (Tune in next week to find out.) Sorry about that, go on.”
Professor: “Does 5 go into or divide into 12 evenly? Well if 12 chunked up into 5 pieces makes a whole number then yes, but in this case it does not because it equals 2.4 and that is neither 2 or 3 which would be the two closest whole numbers on the number line. Does 6 go into 12? (I'm getting tired of saying this but) yes it does, twice, 6 times 2 is 12. We don't need to count any higher than 12 divided by two to see if it's prime so we will stop testing 12 at this point. Wow, I counted 4 numbers that go into 12 (not counting 1 because every whole number is divisible by 1).”
Bob “So what does that mean? “
Professor: “It means we found 4 numbers that go into 12 that make it composite. Now let's look at the number 13 to see if it's prime by following the same steps as we did on 12 (or any other number for that matter.)
I'm going to skip 1 because in our prime number testing algorithm it is not needed. Does 2 go into 13? Unlike 12, no. Same goes for 3,4,5 and 6.
We don't need to test 7 because it is bigger than half of the number we are testing; 2 times 7 is bigger then 13.”
Bob: “Ok, great; so what does that mean?“
Professor: “It means that 13 is a prime number because there are no numbers other than 1 and 13 that evenly go into it.”

Efficiency

Bob: “What's the difference between version 1.0 and 2.11 in your prime number programs? There has to be something different about it that makes 2.11 faster.”
Frank: “Holy Smokes Bob, you are observant. Good thing we got you on the line before the other 687,901 prime people currently on the line. Enough gabble, let's see what the editor has to say.”
Professor: “Thank you Frank. Well, the main difference is how it tests each number to see if they are prime. Version 1.0 uses the same method as described above except:
1) It stops checking to see if the number is prime as soon as we find out that there is a number that goes into it.
2) It only looks up to the square root of the number that we are testing.
For example 12, to see if 12 is prime we only need to count to the square root of 12 which is 3.64101... So we only need to check to see if 2 and 3 go into 12 to determine whether or not 12 is prime.
In version 2.0 and 2.11 I used a different improved method to check if a number is prime. The list of things different include:
1) One of the biggest time savers is that it checks to see if a number is prime only with other primes. In this concept we check 3 to see if it goes into 23 and by checking 3 we also checked 6,9,12,15... and so on.
The square root of 23 is 4.something so we only need to check up to 4.
But we already checked 2, so by checking 2 we checked 4 at the same time without any extra effort. It stores all the prime numbers that it already found in an array so it can be called back up when it needs to see if the next number up is prime.
2) It counts by twos so it does not actually test a number that is already divisible by two. By saving the found known prime numbers to an array it then allows me to do what I want with it. For instance saving it to a file which 1.0 does not do.”
Bob: “The part I don’t understand is why we only have to look to the square root of the number to see if it’s prime or not.”
Frank: “Another good question Bob, I was wondering the same thing myself.”
Professor: “Heh, sorry. Sometimes I start rambling on, expecting everybody to understand what I’m saying. At any rate, the reason why we can do that without losing accuracy is if we take the square root of 100 which is 10, that means 10 times 10 is 100 right? If we test 2 we also tested 50, if we test 3 we also tested 33 and one third, if we test 5 we also tested 20 and so on up to 10. My point is that we already tested the numbers bigger than the square root by first testing the smaller ones.”
Frank: “So you are saying that it's as fast as it can be?”
Professor: “By all means no, you could save some time by first starting with the smallest prime number that you are testing, and multiplying it by itself and stop the loop when it gets bigger than the number you are testing; instead of directly calculating the square root by calling the sqrt (square root) function. However, that won’t affect performance much - if at all. There are also methods that can determine if a number is prime without directly testing it, which would scale linearly in calculation time (which is good because it won’t take much longer as the numbers get bigger.)”
Frank: Well folks, that's all the time we have today on the HPNW Talk Show. Tune in next week to find out what a Perfect number is.