Prime Number Generator v0.2
I wrote this little software that generates as many prime numbers as you want. That’s all it does. Using this software, you can determine the nth prime number, where n can be very, very large. The first version of the software can generate up to around 1014 primes. I have since improved it to remove this limitation. I don’t actually know what is the limitation now, but I’ve tried generating 1034 prime numbers and the program still works! Note though that I haven’t actually let the software generates that many prime numbers. Doing so will take lots of time!
Algorithm
This software doesn’t use any particular mathematical formula to generate the prime numbers. Instead, it checks every single odd number by dividing it with another odd number from 3 to see if that number is divisible without a remainder. As such, the prime numbers it generates is guaranteed to be a prime number, every single one of them.
Speed
I have optimised the algorithm to minimise the software’s processing time, and at current version it is able to generate up to the hundred-thousandth prime numbers and write it to file in just about 1 second on a 2.1GHz dual-core Windows Vista machine.
You have to bear in mind, however, that in order to know what’s the ten-millionth prime number, for example, the software needs to determine all the other 9,999,999 prime numbers that precede that ten-millionth prime. That’s a lot of calculations and iterations to be done, even for a computer.
Screenshots
License
As with all the other contents of this website, this software is licensed under this particular Creative Commons Licence. You are free to share – to copy, distribute, and transmit the software – as long as you attribute the software to me. You may not use the software for commercial purposes. However, I do grant anybody the right to alter, transform, or build upon this software.
Source Code
This software is written in C. Contact me if you want a copy of the source code.
Disclaimer
I do not take responsibility for any loss or damage that results from the usage of this software. No warranty, expressed or implied, is provided with this software.
Download
Click on the appropriate link below to download the software. I assure you the file is virus-free, but as a precaution, you might still want to run a virus check on it using any antivirus software you like, in case the file is tempered with without my knowledge.
Windows: Prime Number Generator
For the technical: MD5 – 94aeb4699bec57617c7a9c312e51a7e5
4 comments
Jordan Thoms said
October 12, 2009 at 12:15 pm (UTC 12)
Nice work – you could look at implementing a Sieve of Eratosthenes (http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes), it should be faster
Syahir Hakim said
October 12, 2009 at 4:16 pm (UTC 12)
Thanks Jordan. I did consider using the Sieve of Eratosthenes, but couldn’t figure out (yet) how to implement it without using a horrible amount of memory for large number of primes.
Because Sieve of Eratosthenes would require listing out all natural numbers up to a limit n and then striking the multiples of prime, if I would like to generate 1 million primes, n would has to be at least 15,485,863. Considering I’m using unsigned long long as the type of variable to store this number, that’s 64 bits per integer. Quick calculation yields 118MB of memory required just to store those numbers. And that’s just for 1 million primes, which is really not that big a number at all. (I quick-calculated the memory that will be required if n is 1 billion – it’s a whopping 8 gigabytes of memory!)
The current trial factoring method that I implement does not store these values at all. Everything is done on the fly, and the values are discarded as soon as they are no longer required. But the downside is of course, the running time is much longer.
I would be very happy to know any suggestions you or anyone might have on the algorithm that can be used to implement the Sieve of Eratosthenes without using impractical amount of memory.
Jordan Thoms said
October 12, 2009 at 4:39 pm (UTC 12)
Ah yes, that’s a good point. I did some research and it seems you can use a segmented version that works on only part of the numbers at a time – eg you could limit it to 50mb of memory. I’m not entirely sure how this works though
. An implementation of this is here: http://www.ieeta.pt/~tos/software/prime_sieve.html
And a few other implementations: http://primes.utm.edu/links/programs/sieves/Eratosthenes/C_source_code/
Syahir Hakim said
October 12, 2009 at 5:52 pm (UTC 12)
Thanks for the links, Jordan. I’ll certainly look at them in detail in due time.
In view of my current workload (I barely started my C project, there’s that truss bridge report and construction to be done, and not to mention final exam is barely 3 weeks ahead), I had to (with difficulty) resist the temptation to work on implementing Sieve of Eratosthenes now.