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;
}

Answer 1

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;