#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();      }I'm trying to find any optimization for my sieve of Eratosthenes code for counting first 100000 prime numbers.The program first mark all even numbers, than square root of max number.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.
Optimization of sieve of Erathosthenes
c++;optimization;primes;sieve of eratosthenes
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;ask * 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;            }        }    }}