Optimization of sieve of Erathosthenes #include &lt;iostream&gt;
    #include &lt;conio.h&gt;
    #include &lt;windows.h&gt;
    #include &lt;math.h&gt;
    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&lt;RUNS;k++)
      {
          c=0; 

      //for (i=0;i&lt;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&lt;100000;i=i+2) z[i]=1; //remove evens
            //now loop through remaing up to square root of max number
            for(i=3;i&lt;316;i=i+2)
            {
            if(z[i]==0) for(j=2*i;j&lt;100000;j=j+i) z[j]=1;
            }
      }

      endtime=GetTickCount();//get finish time
      //calc time
      for(i=0;i&lt;100000;i++)
      {
      if(z[i]==0) {cout&lt;&lt;i&lt;&lt;" ";c++;}
      }
      cout&lt;&lt;"primes found="&lt;&lt;c&lt;&lt;endl;
      totaltime=((float)endtime-(float)starttime)/(1000.0*RUNS);//calculate total time in secs
      cout&lt;&lt;"Totaltime="&lt;&lt;totaltime&lt;&lt;" 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.
if (z[i] == 0)
    for (j = 2 * i; j &lt; 100000; j = j + i)
        z[j] = 1;


can be changed to 

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


as


k * i (with k &lt; 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 (&amp;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 &lt; 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 &lt; SQRT_N; i = i + 2) {
        if (!isNotPrime[i]) {
            for(int j = i * i; j &lt; N; j = j + 2 * i) {
                isNotPrime[j] = 1;
            }
        }
    }
}