Home
This project is a cross platform command line application for finding prime numbers.
The executable usage is found in exe/help.txt or by running prime_finder.exe -h
This is built using GNU make. To build it you need a copy of my "master" makefiles (to save code replication). The two you need are cpp.mk and cpp_utest.mk (only needed to build the unit tests). These can be found in the following repository: https://github.com/davidcorne/MakeFiles
Other than that building should just be a case of typing make at the project directory and an executable will be built in the exe directory. Although it will have the extension .exe if it is build on linux it will run on linux.
The sieve file is an implementation of the Sieve of Eratosthene method of finding primes, more details can be found here: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
The naive class uses a division method by trying to divide the number in question by all the primes lower than it. This uses less storage data as you only need to store the odd numbers. This is however slower than the sieve method.
They are written in C++ using a vector<bool> to store the primes. This is because vector<bool> uses less memory than other containers as it is specilised so that each bool is stored in only a bit. This means that this class can calculate higher primes than if, for example, a vector<int> was used.
Large limits have also been used so that more primes can be calculated, so that this is portable large_int.h defines the largest unsigned integer that can be used and defines LARGE_INT as the largest type of integer.
The following tests were run on a desktop with a AMD Athlon(tm) II X4 605e Processor × 4 and 2.7 GiB of RAM, running 64 bit Windows 7. This used an executable made with OP_FLAGS just -O2 so that there was no debug information and the compilation was optimised twice.
For limits under 100,000 both algorithms registered 0.00 seconds.
| Limit | Naive Runtime (seconds) | Sieve Runtime (seconds) |
|---|---|---|
| 100,000 | 0.015 | 0.000 |
| 1,000,000 | 0.343 | 0.000 |
| 10,000,000 | 8.314 | 0.094 |
| 100,000,000 | 220.834 | 1.311 |
| 1,000,000,000 | 6005.13 | 15.772 |
Here is a graph of the naive alrogithm between the limits of 10,000 and 9,999,000 increasing in intervals of 1,000.
Here is a graph of the sieve algorithm between the limits of 1,000,000 and 1,000,000,000 increasing in intervals of 1,000,000. Note the much larger range, interval and start point than the naive algorithm.
