Sieve of Eratosthenes in C++

Updated June 8th, 2017. This post was introduced to the Reddit /r/cpp soon after I posted and immediately got a feedback saying “both semantically wrong as well as poorly optimized” which is quite true. 🙂  So I’d like to recommend visiting the Reddit link and consider the comments before preceding or even better, refer to the better example introduced here.

Let’s talk about prime numbers. As an application/system software developer, it’s not often to deal with prime numbers in daily working environments. For me, I came across it while solving the Project Euler’s questions.

There’re a lot of good reads on the net describing what prime numbers are, how to get the numbers. So instead of a basic introduction, I’d like to talk about few tricks which can improve the performance of getting prime numbers.

Let’s first talk about the very basic approach to get prime numbers to compare with optimized version later.

You can check whether it’s a prime number or not when a number is given by following:

You’ll also get the Nth prime number based on the isPrime() function above by incrementing the counter when it returns true.

It’s self-descriptive and easy.

Can we improve the performance? Sure! There’s a ‘Sieve of Eratosthenes‘ algorithm, and basically, it does pre-calculate all the non-prime numbers when it found a new prime number by removing all multiples.

Here’s the implementation of the algorithm and its example.

And Lastly, can we improve the Sieve of Eratosthenes algorithm better? Yeah, it’s possible. I first saw the optimized implementation from one of the answers here: http://qa.geeksforgeeks.org/3090/how-to-find-nth-prime-number It’s tricky to understand at first glance in fact. So that I rewrote a little bit and here’s the result:

Comments are still Koreans and will be translated into English soon. Few tricks used to improve the performance are like following:

#1. Check against odd numbers only from line 26 – if (j & 1

#2. Getting the odd number index when an odd number n is given: (n – 3) >> 1

If I changed the unit into ns…

D:\workspace\playground\SieveOfEratosthenes\Release>SieveOfEratosthenes.exe –benchmark_format=json

{

“context”: {

“date”: “06/05/17 01:06:32”,

“num_cpus”: 8,

“mhz_per_cpu”: 2592,

“cpu_scaling_enabled”: false,

“library_build_type”: “release”

},

“benchmarks”: [

{

“name”: “BM_get_nth_prime_without_sieve/10001”,

“iterations”: 160,

“real_time”: 4618235,

“cpu_time”: 4589844,

“time_unit”: “ns”

},

{

“name”: “BM_get_nth_prime_with_basic_sieve/10001”,

“iterations”: 373,

“real_time”: 1854873,

“cpu_time”: 1843164,

“time_unit”: “ns”

},

{

“name”: “BM_get_nth_prime_with_optimized_sieve/10001”,

“iterations”: 1120,

“real_time”: 642190,

“cpu_time”: 655692,

“time_unit”: “ns”

}

]

}

You can access the sample here: https://github.com/heejune/SieveOfEratosthenes

It’ll require the google benchmark and few modifications to correctly link and search headers and libraries to build.

Thanks,

Heejune

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s