Efficiency of sieve of Eratosthenes

Can I make this more efficient?

#include 
#include 
#include 

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).

Listen to your compiler

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

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

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

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])

StackExchange Code Review Q#70738, answer score: 4