Generating Prime Numbers

This post presents a simple implementation of Sieve method used to generate prime numbers.

Simple Sieve Method

With this simple implementation of Sieve method, you can easily generate lists of prime numbers under $10^6$ in less than a second.

The function is templatized by the upper bound of prime numbers looked upon. This allows the use of std::bitset for better memory efficiency. It is not particularly optimised, however, for cache missing etc. Note that the template parameter is set to be type int, using larger numbers like long int may result in stack overflow. One solution is to use dynamic allocation.

Compile with g++ -std=c++14 main.cpp. Run with time ./a.out > prime_list.txt, yielding (on my dual-core laptop):

real    0m0.288s
user    0m0.154s
sys     0m0.131s


Interestingly, the compiler seems to understand the concurrency within this code and parallelizes the work really well. Even if there is no explicit threading, the real time is roughly double the user time.

More Sophisticated Options

If you want to get more juice out of your machine CPU, check out PrimeSieve. It intended to be a highly optimised sieve of Eratosthenes implementation.