# Efficiency of sieve of Eratosthenes

Can I make this more efficient?

#include <stdio.h>
#include <string.h>
#include <math.h>

void setvalue(int array_copy[], int i, int n)
{
int j,p;

for(j = i*i ; j <= n ; j +=(i*2) )
{
array_copy[j] = 1;
}
}

int main()
{
int n,i,l=0,sq;
scanf("%i",&n);

sq = sqrt(n);

int prime_array[n];
int array[n];
for (i = 1; i <= n; ++i)
{
array[i] = 0;
}
for ( i = 4; i <= n; i+=2)
{
array[i] = 1;
}

for( i = 3; i <= sq; i+=2)
{
setvalue(array,i,n);
}
array[2] = 0;
for(i = 2; i <= n; i++)
{
if(array[i] == 0)
{
prime_array[l] = i;
l++;
}
}

for ( i = 0; i <= (l-1) ; i++)
{
printf("%i\n",prime_array[i] );
}
return 0;
}


Disclaimer : most of my comments might be irrelevant as far as performance is concerned but should make your code better on different other aspects (readability for instance).

Compiling your code with gcc -Wall your_file -lm gives me the following warning : sieve.c:7:11: warning: unused variable ‘p’ [-Wunused-variable]. I guess you know the first thing you can do :-).

Making things easier to follow

Splitting your code in small chunks is usually a good idea. Unfortunately, I am not quite convinced by setvalue because what it does is quite complicated and it makes it hard to give it a simple name, to test it out of the algorithm or to reuse it later on. Thus, from my point of view, it's easier to just remove this function.

A good habit : defining things in the smallest possible scope

It is quite common to try to define variables as late as possible and in the smallest possible scope. It prevents whoever reads the code to try to keep in mind the value of irrelevant things and to find what is used for what and it allows one to find easily when a variable becomes unused.

It makes even better if you use c99 as you can them define indices in for-loops.

Also, you can take this chance to define things that go together (such as prime_array and l) together.

Consistency

You should try to be consistent in how you write your code. You should define a way to put space in your code and try to stick to it as much as possible. Consistency is relevant also for braces (you did good), line breaks, incrementations (you used i++ and ++i).

#include <stdio.h>
#include <string.h>
#include <math.h>

int main()
{
int n = 100; //scanf("%i",&n);

int sq = sqrt(n);

int array[n];
for (int i = 1; i <= n; i++)
{
array[i] = 0;
}
for (int i = 4; i <= n; i+=2)
{
array[i] = 1;
}
for(int i = 3; i <= sq; i+=2)
{
for (int j = i*i; j <= n; j+=(i*2))
{
array[j] = 1;
}
}
array[2] = 0;

int prime_array[n];
int l = 0;
for (int i = 2; i <= n; i++)
{
if (array[i] == 0)
{
prime_array[l] = i;
l++;
}
}

for (int i = 0; i <= (l-1) ; i++)
{
printf("%i\n",prime_array[i] );
}
return 0;
}


Keeping things simple

If you just want to write prime number on the standard output, you don't really need a temporary container for the numbers.

Naming things

There are only two hard problems in Computer Science: cache invalidation and naming things. -- Phil Karlton

Naming is really important : here array is a pretty bad name as it doesn't convey any information about how the array is used.

Because of the way you use it, naming it not_prime would probably be a good idea. An even better idea would be to name it prime (or something like that) and use it in such a way that a true-ish value corresponds to prime number and 0 to non-prime numbers. Then you'd get something like :

#include <stdio.h>
#include <string.h>
#include <math.h>

int main()
{
int n = 100; //scanf("%i",&n);

int sq = sqrt(n);

int prime[n];
for (int i = 1; i <= n; i++)
{
prime[i] = 1;
}
for (int i = 4; i <= n; i+=2)
{
prime[i] = 0;
}
for(int i = 3; i <= sq; i+=2)
{
for (int j = i*i; j <= n; j+=(i*2))
{
prime[j] = 0;
}
}
prime[2] = 1;

for (int i = 2; i <= n; i++)
{
if (prime[i])
{
printf("%i\n", i);
}
}

return 0;
}


Algorithm

This is probably where it gets interesting : you have not properly implemented the sieve. At the moment, you apply the logic (from wikipedia) Starting from p, enumerate its multiples by counting to n in increments of p, and mark them in the list (these will be 2p, 3p, 4p, etc.; the p itself should not be marked). for p being the i in for(int i = 3; i <= sq; i+=2) but you should (or you can depending on the point of view) restrict yourself to prime values of i. This corresponds to adding if (prime[i]). This should have a huge impact from a performance point of view.

A tiny problem

There is a variation of the quote above that goes like this :

There are only two hard problems in Computer Science: cache invalidation, off-by-one errors and naming things.

It is relevant in your case because you have an array of n elements so the last index you should access is n - 1. The usual way to write the corresponding loop is with i < n (instead of the equivalent i <= n-1).

The i <= sq stays the same, I'll let you understand why on your own.

The code is now :

#include <stdio.h>
#include <string.h>
#include <math.h>

int main()
{
int n = 122; //scanf("%i",&n);

int sq = sqrt(n);

int prime[n];
for (int i = 1; i < n; i++)
{
prime[i] = 1;
}
prime[2] = 1;
for (int i = 4; i < n; i+=2)
{
prime[i] = 0;
}
for(int i = 3; i <= sq; i+=2)
{
if (prime[i])
{
for (int j = i*i; j < n; j+=(i*2))
{
prime[j] = 0;
}
}
}

for (int i = 2; i < n; i++)
{
if (prime[i])
{
printf("%i\n", i);
}
}

return 0;
}


Even though you have missed an key step in the algorithm, you have tried some fancy optimisation, it would probably be worth commenting on those to explain why and how it works.

I think this will give you the biggest improvement:

for( i = 3; i <= sq; i+=2)
{
// You only have to do the sieve for primes.
// So check array[i] to see if this is a prime.
if (array[i] == 0)
setvalue(array,i,n);
}


Also, your array is too small by one. If you use i <= n and j <= n everywhere, then array needs to be of size n+1.

You also don't need a separate prime_array. You can compact your array without using a copy:

for(i = 2; i <= n; i++)
{
if(array[i] == 0)
array[l++] = i;
}