# Optimization of sieve of Erathosthenes

#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 Im looking for any optimization to make it even quicker.
• Man this comes up a lot. Think its an article I will have to write about :-) – Martin York Feb 12 '15 at 22:34
• Small optimization to your increment. Rather than 'i=i+2 You can use i=i+2 one iteration followed by an i=i+4 the next iteration (because every third increment of 2 is also divisible by 3). So: 5 -> 7 -> 11 -> 13 -> 17 -> 19 ... Basically this is equivalent to cutting out all 2 and 3. – Martin York Feb 12 '15 at 22:37

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

• Great stuff, it worked – skwiot86 Feb 17 '15 at 7:24

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;


## Lack of modularization

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

• the question was for optimisation of the code to find primes faster, not optimisation of whole c++ structure. – skwiot86 Feb 17 '15 at 10:21
• @skwiot86 here reviewers are free to comment on every aspect of the code. – Caridorc Feb 18 '15 at 16:54

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

• Your first and fifth point duplicate one of the already existing answers... Additionally I find your formatting somewhat over the top. Still: nice observations – Vogel612 Feb 15 '15 at 13:25
• @Vogel612 Was doing this on mobile, thus it was somehow tedious to make proper formatting. Also, I wanted to make it more complex - that's why my observations are duplicating. – enedil Feb 15 '15 at 14:14