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.

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax