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 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.
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.