Sieve of Eratosthenes(Prime Sieve)

Sieve of Eratosthenes is used to find all the prime numbers up to a given number N.This method is very efficient than the brute force method(Each number between 2 and N is checked to find if it has any other factors except 1 and itself). The basic concept behind Sieve of Eratosthenes is the fact that a prime number has no other factors except 1and itself. So, if we mark multiples of all the numbers less than N, the unmarked numbers will be prime numbers.

To find all the prime numbers upto N, we can start with the following steps

Algorithm

Step 1 – Intialise mark[]

Initialise mark[] array with 0(All numbers are unmarked initially).

Step 2 – Mark multiples

Mark multiples of all the numbers between 2 and sqrt(n).We do not need to go beyond sqrt(n) because every non prime number has atleast one factor(other than 1)less than its square root.

We need to mark multiples of unmarked numbers only because multiples of marked numbers have already been marked. (For example, 4 and 8 will be marked as a multiples of 2, therefore we do not need to mark 8 as a multiple of 4 again)

Step 3

All the unmarked numbers are prime numbers.

Code for this can be written as:

void sieve(int n)
{
    int mark[100000]={0},i,j;/*Initialise mark array with 0*/
    /*mark multiples of numbers between 2 and sqrt(n)*/
    for(i=2;i*i<=n;i++)
    {
        if(mark[i]==0)
        {
            for(j=i*2;j<=n;j+=i)
                mark[j]=1;
        }
    }
    printf("The prime numbers are");
    for(i=2;i<=n;i++)
    {
        if(mark[i]==0)
            printf("%d ",i);
    }
}

This code can be further optimised as follows:

  1. For each i, marking of multiples should start from i*i since multiples less than i*i have one factor less than i and hence have already been marked by some other i.
  2. All multiples of 2 can be marked separately and then i can be iterated for odd numbers only starting from 3.
  3. Since i will be odd,so will be i*i. So, j can be incremented by 2\i every time because even numbers have already been marked.(sum of even and odd is always odd).

The final code can be written as:

void sieve(int n)
{
    int mark[100000]={0},i,j;/*Initialise mark array with 0*/
    /*Mark all the multiples of 2*/
    for(i=2;i<=n;i+=2)
        mark[i]=1;

    /*mark multiples of odd numbers between 3 and sqrt(n)*/
    for(i=3;i*i<=n;i+=2)
    {
        if(mark[i]==0)
        {
            for(j=i*i;j<=n;j+=2*i)
                mark[j]=1;
        }
    }
    printf("The prime numbers are");
    for(i=2;i<=n;i++)
    {
        if(mark[i]==0)
            printf("%d ",i);
    }
}

This content has been helpful to you?

Thanks for contributing!

Yes No