Sieve of Eratosthenes Algorithm

ALGORITHM Sieve(n)

//Implements the sieve of Eratosthenes

//Input: A positive integer > 1

//Output: Array L of all prime numbers less than or equal to n

for p ← 2 to n do A[p] ← p

for p ← 2 to √n do 

if A[p] = 0 //p hasn’t been eliminated on previous passes

j ← p ∗ p

while j ≤ n do

A[j] ← 0 //mark element as eliminated

j ← j + p

//copy the remaining elements of A to array L of the primes

i ← 0

for p ← 2 to n doifA[p] = 0

L[i] ← A[p]

i ← i + 1

return L

Method:

Algorithm to find all the prime numbers less than or equal to a given integer n by Eratosthenes’ method:

1.     Create a list of consecutive integers from 2 to n: (2, 3, 4, …, n).

2.     Initially, let p equal 2, the first prime number.

3.     Starting from p², count up in increments of p and mark each of these numbers greater than or equal to p² itself in the list. These numbers will be p(p+1), p(p+2), p(p+3), etc..

4.     Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise, let p now equal this number (which is the next prime), and repeat from step 3.

C  program:

//  C program to print all primes smaller than or equal 

//to n using Sieve of Eratosthenes

#include <stdio.h>

#include <stdlib.h>

void SieveOfEratosthenes(int n)

{

    // Create a integer array "prime[0..n]" and initialize

    // all entries it as 1(true). A value in prime[i] will

    // finally be 0(false) if i is Not a prime, else true.

    int prime[n+1];

    int p,i;

for(i=0;i<=n;i++)

{

    prime[i]=1;

}

    for (p=2; p*p<=n; p++)

    {

        // If prime[p] is not changed, then it is a prime

        if (prime[p] ==1)

        {

            // Update all multiples of p greater than or

            // equal to the square of it

            // numbers which are multiple of p and are

            // less than p^2 are already been marked.

            for ( i=p*p; i<=n; i+= p)

                prime[i] = 0;

        }

    }

    // Print all prime numbers

    for (p=2; p<=n; p++)

       if (prime[p]==1){

          printf("%d ",p);

}

}

int main()

{

    int n;

    printf("Enter the N value\n");

    scanf("%d",&n);

    printf("Following are the prime numbers smaller than or 

equal to %d\n",n);

    SieveOfEratosthenes(n);

    return 0;

}  

Output:

Enter the N value

30

Following are the prime numbers smaller than or equal to 30

2 3 5 7 11 13 17 19 23 29