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

μœˆλ„μš° λ“œλΌμ΄λ²„ μ½”λ“œ 사이닝 μ‹€μš© κ°€μ΄λ“œ

μœˆλ„μš° μ½”λ“œ 사인은 λ³΅μž‘ν•©λ‹ˆλ‹€. μœˆλ„μš° μ½”λ“œ 사인이 λ³΅μž‘ν•œ μ΄μœ λŠ” 기술의 λ³΅μž‘λ„κ°€ λ†’μ•„μ„œλΌκΈ° 보단, 그것이 기반으둜 ν•˜κ³  μžˆλŠ” μœˆλ„μš° μ½”λ“œ μ‚¬μΈμ˜ 정책이 μœˆλ„μš° λ²„μ „λ§ˆλ‹€ λ‹€λ₯΄κ³  λ³΅μž‘ν•΄μ„œ 일 것이기 λ•Œλ¬Έμž…λ‹ˆλ‹€.

μ € μ—­μ‹œ 컀널 λ“œλΌμ΄λ²„ 사인 이슈둜 λ‹€μ‹œ μ˜ˆμ „ 지식을 ν™˜κΈ°μ‹œν‚€λ €κ³  λ…Έλ ₯ν•˜λ‹€κ°€, μΈν„°λ„·μ—μ„œ 쒋은 글을 ν•˜λ‚˜ λ°œκ²¬ν•˜κ²Œ λ˜μ—ˆκ³  원 μ €μžμ˜ ν—ˆλ½μ„ 맑아 λ²ˆμ—­μ„ ν•˜κ³  κ·Έ κ²°κ³Όλ₯Ό 이곳에 올리게 λ˜μ—ˆμŠ΅λ‹ˆλ‹€.

원본 글은 http://www.davidegrayson.com/signing/ 이곳에 μžˆμŠ΅λ‹ˆλ‹€. 포맷이 λ°”λ€Œμ–΄ λ²„λ¦¬λŠ” 이슈둜 인해 PDF둜 κ²°κ³Όλ₯Ό μ—…λ‘œλ“œ ν•©λ‹ˆλ‹€.

μœˆλ„μš° λ“œλΌμ΄λ²„ μ½”λ“œ 사이닝 μ‹€μš© κ°€μ΄λ“œ

κ°μ‚¬ν•©λ‹ˆλ‹€.

heejune