Index of primes links 
Every few months I get a message from someone desiring a program that will produce a complete list of all the prime numbers that can be represented by a 64 bit number. Small Prime Finder produces a list of all the 31 bit numbers so it should be a simple matter to produce a 64 bit version - right? Well, the programming is trivial. The problem would be in convincing anyone to run the program to completion.
Small Prime Finder was written several years ago when a 300MHz Pentium was state-of-the-art and programming tools seldom had support for anything larger than 32 bits. 31 bits was "chosen" as the limit because the programming tool used (Delphi 2) had a 32 bit long integer (-2,147,483,648 - 2,147,483,647) but no 32 bit unsigned integer (0 - 4,294,967,295).
On that 300MHz machine every 31 bit prime could be calculated in about 12 hours. Today's machines are an order of magnitude faster and can run the program to completion in about an hour. So why not go to 64 bits? The tools are available. Doubling the calculations would only take a couple of hours. Yes, doubling the calculations would only double the time but 64 bits is not twice 32 bits. 33 bits is significantly more than twice 32 bits!
To go from 31 bits to 32 bits means that we need to check all the numbers between 2,147,483,647 and 4,294,967,295. That's 2,147,483,648 possible numbers! The same number as the original program checked in total! To go to 33 bits would require checking 4 times the number of possible primes. 64 bits would take...
But it gets worse. To check a number for primacy, Small Prime Finder divides by all primes smaller than the square root of the number. For a 31 bit number this is about 4800 trial divisions. Since half the possible primes in a 31 bit set contain a 1 in the high order bit (the number is larger than 1,000,000,000), the average number of divisions for all 31 bit numbers is almost 4800. Going to 32 bits changes this average to about 6500 checks. So if Small Prime Finder now runs in an hour, a rough estimate of the time to calculate all 32 bit primes would be 1 hour * 2 * 6500/4800 = 2.7 hours. Not bad. 33 bits would take 2.7 times longer or a little over 7 hours. 64 bits would take...
So the problem isn't going through the program and changing all occurrences of LongInt to Int64 and then verifying the result. The problem is in finding someone who wants to spend the next 20,000,000,000 YEARS waiting for the program to produce the desired result. But maybe computers will get faster in the next 20 BILLION years. In fact, if the speed of computers keeps doubling every 18 months, then 40 years from now we will have computers fast enough to run the program in less than 300 years. And 6 years after that it will take less than 20 years. So this sounds like a programming project for our grand-children to give to their children.
But if you still insist on a 64 bit version, I am working on one where you can specify a range to check. The problem is where to store the 105,097,565 primes that have to be used for the trial divisions. I'm thinking I need a storage compression method because most people don't have 840MB of RAM to spare and hard disk access is out of the question if we want this done in hours rather than years. Even then it will still take about 6 hours to check a range of numbers that the current program checks in 1 second. But if we were willing to take 12 hours years ago, maybe someone would be interested in a program that calculates all primes in a small range in a day or so.
So, if you think my math is wrong, or computer speed is increasing faster than doubling every 18 months, or the Webboret from the planet Qwexrev are about to reveal a new field of mathematics that will make Einstein look like a German patent clerk, please feel free to email me. Answering should be more interesting that repeated explanations of "Why don't you write a 64 bit version of the program?" to people who never understood compound interest.
Please
email [email protected]
with comments and corrections.