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.

• Loki Astari: Man this comes up a lot. Think its an article I will have to write about :-)
• Loki Astari: 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.

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

• skwiot86: Great stuff, it worked

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.

• skwiot86: the question was for optimisation of the code to find primes faster, not optimisation of whole c++ structure.
• Caridorc: @skwiot86 here reviewers are free to comment on every aspect of the code.

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;

• Vogel612: Your first and fifth point duplicate one of the already existing answers... Additionally I find your formatting somewhat over the top. Still: nice observations
• enedil: @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.