Literally, Sieve is “A utensil for separating the finer and coarser parts of a pulverized or granulated substance from each other”. Eratosthenes, a Greek Mathematician, came up with such a sieve to filter out Prime numbers from a given set of integers. The process/algorithm came to be known as Sieve of Eratosthenes!
The Algo is pretty simple, start with number 2, cross all its multiples (till MAX_NUMBER), proceed with the next number 3 and cross all its multiples too and so on. The remaining numbers in the set will be primes. The algo itself brings in some optimizations!
1. All even numbers get cancelled in first iteration for 2. Next number (3) onwards, start directly checking for multiples starting with the square of the number.
2. The multiples need to be crossed for numbers < square root (MAX_NUMBER), because rest of the multiples would have got crossed earlier itself.
The code in Java for the Sieve of Eratosthenes is as follows:
public class SieveEratosthenes {private static final int MAX_NUMBER = 1000;public static void main(String[] args) {boolean[] arr = new boolean[MAX_NUMBER];int i, j;//Initialize the Boolean array to TRUE (i.e. Prime)for (i = 0; i < arr.length; i++)arr[i] = Boolean.TRUE;//Finish with all divisors of 2 to optimize code for the remainingfor (i = 2; 2 * i < MAX_NUMBER; i++)arr[2 * i] = Boolean.FALSE;//Only odd numbers need to be considered in both loops, since// Odd * Even = Even//And all evens are covered as multiples of 2for (i = 3; i < (Math.sqrt(MAX_NUMBER)); i += 2) {for (j = i; j * i < MAX_NUMBER; j += 2)arr[j * i] = Boolean.FALSE;}System.out.println("The primes below " + MAX_NUMBER + " are : ");int count = 0;for (i = 2; i < arr.length; i++)if (arr[i]) {System.out.println(i);count++;}System.out.println("The total no of primes till " + MAX_NUMBER + " are : " + count);}}
