Prime Number Generator

A couple years back I wrote a C++ program that generated a list of all the prime numbers up to a specified maximum. I was hoping to dredge up the code for it and post it here, but alas, it seems to have vanished from my hard drive, and I no longer have the knowledge to write such code. For computer science people, such a program would be child's play, but it was a challenge for me. Since I can't reproduce the code, I'll just describe the process I devised, which not only calculated the primes but did it in what I think was the most efficient way possible.

First the program asked for a maximum value -- the point above which the program would stop checking for primes and terminate. The higher the number, the longer the program would run. The program would then test a sequence of numbers, starting with 3. (1 was skipped, and 2 was a given.) The easiest way to check to see if a number is a prime (in terms of ease of coding) is to check every positive whole number (except for 1) below its value to see if any are divisors. If not, then you have a prime. That works, but the process is much slower than it needs to be. I gradually worked out what I believe to be the fewest number of division tests necessary.

First of all, I reasoned that I would not have to check beyond values that were more than one half the number, since such values multiplied by 2 (the lowest possible divisor) would exceed the given value. Okay, then what about one third? In that case, as long as I checked for 3 as a divisor, then anything above one third could be skipped. Following this logic to its inevitable conclusion, I finally realized that it would never be necessary to check for any divisor greater than the value's square root, because obviously if the square root were multiplied by a value greater than itself, its product would have to be greater than the value being tested. Once again, any mathematician could probably tell you this off the top of her head, but I'm no mathematician, and I worked it out for myself. So I'm moderately proud of myself.

But that's not all. It is possible to further reduce the number of tests by only testing primes as divisors. After all, any non-prime number can be factored into primes, so it is redundant to check with non-primes. Now we have an interesting situation. Since the purpose of the program is determine which numbers below a certain value are primes, it would be silly to embed a list of primes into the program. That would totally defeat the purpose. (Although one might argue that it would make sense to include a short sequence of the smallest primes to speed thing up.) My solution was to use the primes as they were determined by the program. In other words, instead of just printing a number on the screen as soon as it was determined to be a prime, I had the program store it in an array (a list of values) to which it could refer.

Here is what the program did:

1. Take a value (starting with 3).
2. Determine that number's square root.
3. If the square root is not a whole number, round it down to the nearest whole number.
4. Refer back to the list of prime numbers which have already been determined. (2 is there by default.)
5. Take each prime number that is less than or equal to the rounded down square root of the value being tested and see if it is a divisor of that number. In other words, can it be divided into that number without there being a remainder.
6. If there is no remainder [for one of the divisors], then that value is [not] a prime number, and it is [not] added to the array. No further tests are made of it.
7. If all possible tests have been done, and all the divisors result in a remainder then the value is not a prime number and is not added to the array.
8. Increment the value by one.
9. If the value is greater than the stated maximum for this run of the program, print the array to the screen and/or a file, and terminate the program. Otherwise go to step 2.

Now wasn't that incredibly interesting? (I know it wasn't, but if I can't blather on occasionally in my own blog, where can I?) In any case, if anyone out there actually read this and knows of any further ways the process of finding primes can be streamlined, I would be thrilled to hear from them.