SEIVE OF ERATOSTHENES

SEIVE OF ERATOSTHENES

Suppose, we need to find all the prime numbers upto a very large number N. We first make a boolean array primes[N] and initialize each element to say ‘true’. Now we run an outer for loop from i=2(the first prime number) to i<=sqrt(N) and in each loop we check that for the value of primes[i], if it is true then we run another nested loop from j=i^2 till j<=N and increment the loop-counter of inner nested loop by i; and within this inner loop set primes[j] = false.

When the algorithm terminates, all the numbers in the ‘primes’ array that are ‘true’ are prime.

ALGORITHM:

Input: an integer n > 1

Let A be an array of Boolean values, indexed by integers 2 to n,

initially all set to true.

 for i = 2, 3, 4, ..., not exceeding √n:

  if A[i] is true:

    for j = i², i²+i, i²+2i, ..., not exceeding n :

      A[j] := false

Output: all i such that A[i] is true are prime.

Implementation in Java

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

public class Main

{

     public static void main(String[]args)throws IOException

     {

          BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

          System.out.print("Enter N : ");

          int n=Integer.parseInt(br.readLine());

          boolean primes[]=new boolean[n+1];

          /* primes[0] and primes[1] should be false by default

           * because they 0 and 1 are not primes.

           */

          for(int i=2;i<=n;i++)

              primes[i]=true;

          for(int i=2;i*i<=n;i++)

              if(primes[i])

                   for(int j=i*i;j<=n;j+=i)

                        primes[j]=false;

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

              if(primes[i])

                   System.out.println(i);

     }

}