Custom Sieve of Eratosthenes

Question

I'm trying to improve my code to find all the prime numbers within a set range as fast as possible, and I am trying to make it even faster. On my github page here, I have some optimization settings within Visual Studio that help improve the speed.

#include <iostream> #include <fstream> #include <Windows.h> #include <conio.h> #include <bitset> #include <string> #include <math.h> #define RUNS 10000 // How many times the code will runs. I use run each section of code a set number of times, divide by that number // to get the average. I had to to this because the program was running too fast for the GetTickCount() to get a speed. #define RANGE 100000 // What number of primes to search up to #define R2 RANGE/2 #define BRUNS 100000 int main() { //Set up varibles int count; char primes[RANGE]; int searchRange = sqrt(R2) + 1; DWORD starttime, endtime; //############################ SIEV ################################# starttime = GetTickCount(); for (int k = 0; k<RUNS; ++k) { count = 0; memset(primes, 0, R2); for (int i = 0; i < searchRange; ++i) { if (primes[i] == 0) { for (int j = (i << 1)*i + (i << 2) + (i << 1) + 3; j<R2; j += i * 4 + 6) { primes[j] = 1; primes[j + i * 2 + 3] = 1; } } } } endtime = GetTickCount(); for (int i = 0; i<R2; i++) if (primes[i] == 0) count++; float totalOp = ((float)endtime - starttime) / (1000 * RUNS); //##################################################################### //#################### MEMSET FUNCTION TIMING TEST #################### // Here I am timing how long the memset function takes, so I can take that off the time for the sieve float totalMemset = ((float)endtime - starttime) / (1000 * RUNS); //##################################################################### //#################### OUTPUT TIME AND PRIMES ###################### std::cout << "Optimised Sieve Time: "; std::cout << totalOp; std::cout << "\nPrimes Found: "; std::cout << count + 1; //##################################################################### _getch(); return 0; }

Why the check primes[i]==0? Isn't it possible that the value in memory will be 0 even if it's not in the address range from 0 to R2-1? — Myridium
– Myridium, Commented Oct 17, 2016 at 14:35

Toby Speight · Accepted Answer · 2018-04-05 07:59:54Z

Missing header

Include <cstring> to get a definition of std::memset (and add the missing namespace qualifier where you use it).

Unused headers

We're not using <bitset>, <fstream> or <string>.

Prefer C++ headers

Use <cmath> in preference to <math.h> for new code, to place the identifiers into the std namespace (the only identifier that needs updating where it's used is std::sqrt).

Non-standard headers

Instead of platform-specific headers, you can use Standard C++ <chrono> for timing the code:

#include <chrono> int main() { auto const starttime = std::chrono::high_resolution_clock::now(); do_work(); auto const endtime = std::chrono::high_resolution_clock::now(); auto const time_in_ms = std::chrono::duration_cast<std::chrono::milliseconds>(endtime - starttime); std::cout << "Time taken: " << time_in_ms.count() << " ms\n"; }

Unused variable

We never use totalMemset - leaving it in makes your code look like it's not really ready for review.

Use unsigned types

Most of the numbers used in this program are necessarily non-negative. Prefer unsigned types to make this more apparent (and to give you twice as much range of values).

Prefer constants to preprocessor macros

This is better, as it's strongly typed, and won't be expanded in the wrong context:

const std::size_t RUNS = 10000;

Use `*` for arithmetic, not `<<`

An optimising compiler should generate the same code for

int j = (i << 1)*i + (i << 2) + (i << 1) + 3;

as for

int j = 2*i*i + 4*i + 2*i + 3;

The latter more clearly conveys your intent (and you could collect 4*i + 2*i to simply 6*i). Don't attempt to micro-optimize this!

Prefer range-based `for`

Instead of counting elements like this:

int count; for (int i = 0; i<R2; i++) if (primes[i] == 0) count++;

Here's a simpler form:

std::size_t count = 0; for (auto n: primes) count += !n;

Stack Exchange Network

Custom Sieve of Eratosthenes

1 Answer 1

Missing header

Unused headers

Prefer C++ headers

Non-standard headers

Unused variable

Use unsigned types

Prefer constants to preprocessor macros

Use `*` for arithmetic, not `<<`

Prefer range-based `for`

You must log in to answer this question.

Hot Network Questions

Custom Sieve of Eratosthenes

1 Answer 1

Missing header

Unused headers

Prefer C++ headers

Non-standard headers

Unused variable

Use unsigned types

Prefer constants to preprocessor macros

Use * for arithmetic, not <<

Prefer range-based for

You must log in to answer this question.

Related

Hot Network Questions

Use `*` for arithmetic, not `<<`

Prefer range-based `for`