# Custom Sieve of Eratosthenes

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 Oct 17 '16 at 14:35

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

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

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

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;