Optimization of sieve of Erathosthenes

Question

#include <iostream>
    #include <conio.h>
    #include <windows.h>
    #include <math.h>
    using namespace std;
    #define RUNS 1000
    char z[100000];
    int i,j,k,c;

    void main(void)
      {
      DWORD starttime,endtime;
      float totaltime;

      starttime = GetTickCount();//get start time
      for(k=0;k<RUNS;k++)
      {
          c=0; 

      //for (i=0;i<10000;i++) z[i]=0; //clear array
      memset(z,0,100000);
        z[0]=1; // 0 is not a prime
        z[1]=1;  // 1 is not a prime
            //now remove all evens from 4 up
            for(i=4;i<100000;i=i+2) z[i]=1; //remove evens
            //now loop through remaing up to square root of max number
            for(i=3;i<316;i=i+2)
            {
            if(z[i]==0) for(j=2*i;j<100000;j=j+i) z[j]=1;
            }
      }

      endtime=GetTickCount();//get finish time
      //calc time
      for(i=0;i<100000;i++)
      {
      if(z[i]==0) {cout<<i<<" ";c++;}
      }
      cout<<"primes found="<<c<<endl;
      totaltime=((float)endtime-(float)starttime)/(1000.0*RUNS);//calculate total time in secs
      cout<<"Totaltime="<<totaltime<<" sec\n";

      printf("Press any key to end");

      getch();
      }

1. I'm trying to find any optimization for my sieve of Eratosthenes code for counting first 100000 prime numbers.
2. The program first mark all even numbers, than square root of max number.
3. The program already does take fraction of the seconds to count these prime numbers, but I`m looking for any optimization to make it even quicker.

Answer 1

if (z[i] == 0)
    for (j = 2 * i; j < 100000; j = j + i)
        z[j] = 1;

can be changed to

if (z[i] == 0)
    for (j = i * i; j < 100000; j = j + 2 * i)
        z[j] = 1;

as

• k * i (with k < i) is already set to 1 by sieve k.
• when j is odd, j + i is even and so already set by even sieve.

For readability, you may split into function and do some renaming, to have something like:

const int N = 100000;
const int SQRT_N = 316;

void shieve(char (&isNotPrime)[N])
{
    memset(isNotPrime, 0, N);
    isNotPrime[0] = 1; // 0 is not a prime
    isNotPrime[1] = 1; // 1 is not a prime
    // now remove all evens from 4 up
    for (int i = 4; i < N; i = i + 2) {
        isNotPrime[i] = 1; // remove evens
    }
    // now loop through remaing up to square root of max number
    for (int i = 3; i < SQRT_N; i = i + 2) {
        if (!isNotPrime[i]) {
            for(int j = i * i; j < N; j = j + 2 * i) {
                isNotPrime[j] = 1;
            }
        }
    }
}

Answer 2

In C++ you should use constants instead of #define

#define RUNS 1000

should become

const int RUNS = 1000

---

Loop variables should be declared in the smallest scope possible, not at the top of the file.

---

Always use braces, the following line is not easy to modify:

if(z[i]==0) for(j=2*i;j<100000;j=j+i) z[j]=1;

---

using namespace std;

Is considered bad practice.

---

Lack of modularization

All your code is top level , you should use more functions to facilitate reuse.

Answer 3

1

At first, do not use using namespace std.

2

You do not use any function from "math.h" header so you do not need to include it.

3

Next, using #include <windows.h> is also bad. You use it only for time measure. Standard C++ library has a dedicated header for this purpouse. It will make code more portable. Example:

#include <chrono>

// ... some code

auto startTime = std::chrono::high_resolution_clock::now();

// do calculations

auto endTime = std::chrono::high_resolution_clock::now();

// output

auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(endTime - startTime).count();
std::cout << "Total time: " << duration << " milliseconds.";

4

main function should always return int, and accepted arguments are either none or

(int, char* [])

5

Instead of #define macro, C++ uses const keyword:

const int runs = 1000;