OBJECTIVE: To create a decent, relatively fast prime number calculator.
Updated: Feb. 28, 2006. See "Updates" for more details.
NOTICE: Downloads of the C version between Feb. 25 and Feb. 28 may contain a bug which causes the program to run a little too fast and calculate non-primes. The updated .zip file is below, and the page has been changed to reflect the benchmarks.
Downloads
New. Recommended: Download the prime number program in written in C. It is in a .zip file, so you'll need WinZip (link below) to download it. Note that you should read the readme! You do NOT need the Visual Basic runtime files to run this version! When the black box comes up, type the number you want to calculate up to and press enter. The program will calculate and quit. There is a textfile option as well!
Download the original prime project compiled .EXE. This file is a program that calculates all prime numbers up to a value you specify. If you're interested in calculating your own prime numbers on your computer, and/or saving them to a text file, printing them, or frolicking about with the thousands and thousands of pages of primes you printed and innocent trees you killed using up all that paper, this is your download. When you save primes, it outputs them into a "primes.txt" in the directory you run the program from. Don't run it from a temporary folder (that is, opening it instead of saving it) because you won't be able to save them if you want to. (24KB, recommended for slow connections)
Other downloads: Source code now available for any programmers interested in how it works (Visual Basic 6 required, or text editor to view contents only). (3KB)
Primes up to nine million can now be downloaded (though you should make every effort not to) if you do not wish to calculate it. (WARNING: file approaching 2 MB, NOT RECOMMENDED for slow connections). I do warn you, these are the first 602,000 or so primes.
ZIP file woes...
If your computer cannot read a .zip file...
You'll need WinZip or WinRAR (your choice, I prefer WinRAR) to unzip the source code or the lists of primes. The finished program itself, however, is not zipped, so you won't need to download anything new if you're only interested in calculating primes by yourself.
Updates
Actually, I've had this for quite some time; two weeks. I rewrote the prime number program to operate under the C programming language.
That means a few things.
You can now calculate primes up to 20 million, that is, 20,000,000, in under two minutes.
I added the prime number program in C to the downloads area below; it is the FASTEST one yet! Don't bother with the pretty-looking Visual Basic one if all you want to do is calculate massive numbers of primes fast!
Oh, please, please, please; read the README.txt file included in the zip file. You need to run the .bat files (the screw-looking icons) if you want to calculate primes; primes.bat and primetxt.bat for on-the-fly and textfile output, respectively. Have fun!
Origins
Hello, and welcome to my prime number page. Here, you can download the prime program I spent about two days developing as proof (to whom, I don't know) that I could write an improvable algorithm which decreases processing time and increases performance in each build.
The result was the prime number project.
By the way, before I begin: This program uses no "special" algorithm. Just repeated "mod" functions to check the remainder of the repeated division operations. Is there a faster way? There is no doubt in my mind there is. This is just a simple method I developed to calculate primes (a primality test).
Disclaimer: ANY HARM DONE TO YOUR COMPUTER THROUGH THE USE OF THIS PROGRAM, THOUGH EXTREMELY UNLIKELY, IS NOT THE RESPONSIBILITY OF THE DEVELOPER!
What Is It?
First, let's review.
Division. You have the dividend - what's being divided, the divisor - what you divide by, and the quotient - the "answer." So in 6 / 3 = 2, 6 is the dividend, 3 is the divisor, and 2 is the quotient.
Going a bit further, a dividend is said to be "divisible" by a divisor when the quotient is a whole number. That is, the divisor goes "evenly" into the dividend. In this case, the divisor and the quotient are said to be factors of the dividend. 2 and 3, for example, are factors of 6, because 2 times 3 equals 6. Similarly, 5 times 20, 10 times 10, and 4 times 25 all equal one hundred, therefore each pair can be considered factors of one hundred.
A prime number is a number with no factors except for one and itself (because 1 times any number is that number [a multiplicative identity if you wish to go further into that]). If a number cannot be broken down any further into new factors, and cannot be divided evenly by anything other than one and itself, it is considered to be "prime."
2 is the only even prime since every even number is divisible by 2 (in fact, programmers who download the source will see I have a little mathematical "proof" in there to establish two as a prime). So when writing a prime number program, you can ignore even numbers altogether.
If you eliminate all even numbers, you don't have to bother dividing by them, because no odd number is evenly divisible by two. So you need only to divide by odds.
On top of that, you need not divide by every odd number. All you really need to do is divide by primes. Why?
Prime factorization is the process of hunting down all the prime factors in a number (that is, obviously, prime numbers that multiply out to be that number). If you wanted to complete the prime factorization for 68, you could break it into 2 times 34, which is 2 times 2 times 17, thereby breaking 68 down as far as possible.
So since prime numbers are the "building blocks" of all other numbers, you can check if a number is prime by dividing it by other prime numbers.
If a number is evenly divisible by any prime numbers, it is not prime. So, if we eliminate all the non-primes, we're left with the primes.
When do you stop checking to establish a number is prime? Well, you could go all the way up to one less than the number you're checking. This is, however, unnecessary and time-consuming. You need only to check up to the square root of the number you're testing. Wikipedia explains a lot more.
There you go. That's how it works. Now, when the numbers get rather large, the number of operations on each number continues to increase due to the ever-increasing number of primes below the square root of that number.
On top of that, the algorithm I wrote is extremely recursive, meaning you need to know all the prime numbers below the square root of the number you're testing to make it work properly. Wikipedia has an excellent article on primality tests, which are tests to check if a number is prime. Basically, the program here is a bunch of primality tests jumbled into one. There's a faster way to find primes, I'm sure, but for now, this is good.
History
It started in VBA. I wrote a very simple prime number calculator which processed every number up to the number the user specified by checking if the remainder was zero when it was divided by every number up to one half of itself. If the remainder was zero, it would quit and go to the next one.
To get to 20060 (why I chose that number, I don't know), it took 102 seconds.
I then simplified it by only processing odd numbers. It was down to 75 seconds to get to 20060.
I then simplified it by DIVIDING by only odd numbers and removing a "DoEvents". Went down to 36 seconds.
Simplified it again by dividing only by prime numbers. Guess what it went down to. "0" seconds.
I needed bigger numbers. I tried, this time, 200060. 32 seconds on a 1.6GHz machine in VBA.
Time to bring it over to VB6 and compile it. I added a ginormous array to hold all the prime numbers instead of just printing it to the textbox like I had done before. Then I switched the textbox over to a listbox since I wasn't having much luck with "vbNewLine". Added some code to make it frilly and tell you how many primes it found (which increased processing time). Removed all DoEvents, other than printing to a listbox. I was confident. Compiled the .EXE. The result:
Primes up to 200060 on a 450MHz machine took a mere 15 seconds. I had to try it on the 1.6GHz machine.
And that took a mere 3 seconds. I had to try bigger numbers. A million.
58 seconds. And then I ran into an error. There were over 33,067 primes, thus the listbox would not be able to hold all the primes. For a number of primes over 33067, I do not print to the listbox. I then added functionality to print to a "Primes.txt" text file in the same directory.
February 6th, 2006: Fixed the executable to run much faster. Down to "0" seconds again calculating 1 million on my 1.6GHz machine, so I went to nine million. That took a mere 36 seconds. The results of both are posted above. Try not to download them, though. If you have at least a 300MHz PII (or equivalent) with a decent amount of RAM (32MB), you should be fine in calculating up to a million or so. It took my "slow" machine only seven seconds for the million, and that's a 450MHz PIII with 64MB RAM under Win98.
How does the fix work? Well, it seems I ignored logic in writing programs. That's the best way to describe it. The removal of an old conditional statement that did absolutely nothing (or two, or three...) made it a lot faster than I expected.
February 25th, 2006: I've actually had this for a while, but only now have I decided to get around to updating the webpage with it. I rewrote the prime number program in a different programming language (C, compiled with GCC) to make it run a bit faster (Visual Basic is comparably slower).
I have no C skill, but I managed to churn out a new version sometime before Valentine's Day of this year (2006), and I recently updated the page with it. Now you can calculate primes a lot faster. The greatest improvement should be seen on Win95/98 machines, and it is still compatible with all other 32-bit versions of Windows. Unix, too, can run it, but then again, why are you running Unix. (No need to e-mail me over it, it was a joke.)
I recommend downloading the C version of the program as I won't update the VB version as much. Also note the source code that is available for download for the Visual Basic version is very much outdated compared to what the actual program is based on, and I plan to update both soon.
But still, the C version is the fastest yet, and it comes with source if you want it; I suggest you download it if you want to skimp on the user interface and do some hardcore prime calculation. If you want a time reference to look at, on a 1.6GHz P4 machine with 256MB RAM, primes up to 20,000,000 took around 80-85 seconds, and the resulting textfile was 11.5 MB small (counting the newline characters after each number and the prime count at the end). The new build unfortunately does not tell you how fast it calculated the primes. Sorry, I haven't the C knowledge to figure it out.
Why?
A few reasons. One would be free time. The other, curiosity. The final reason: My seventh grade math teacher. He had the first ten thousand printed and hung up on the wall in the classroom. He said a kid with "a lot of free time" had given it to him.
I wanted to prove (years in the future) that I had more free time. I think I won.
Anyway, I certainly do hope it is of interest to someone somewhere. It operates upon a very simple concept, and is a very simple, yet improvable algorithm.
Closing Notes
Both the Visual Basic version and the C version appear to "hang" or freeze up for large calculations, and tend to use up all of the processor's resources. If you want to cancel calculation, simply close the program, then click "End Now" when the error message comes up. Windows will always report that the program is not responding. This is not a bug. It won't respond to user-generated events because it's busy calculating prime numbers!
For whatever reason, though, it does not tend to slow down other applications (well, basic applications). So feel free to work as your computer busily crunches numbers.
Oh, if you find a bug, like it crashes or you're calculating non-primes, e-mail me: STufaro@gmail.com.
Please do not link directly to the .exe or the .zip files; linking to this page instead and giving directs would be much appreciated!
Contact
If you have any questions about either version of the program, please e-mail me at STufaro@gmail.com.
people were potentially interested in calculating prime numbers. Weirdos.
