Pages

Thursday, November 23, 2017

Sieve of Eratosthenes In Java

The sieve of Eratosthenes is a famous ancient algorithm to find all prime numbers up to a given limit. We are going to implement this algorithm in Java.


Steps we will follow:

a) Lets we have an array of size 25.
b) First start with 2, remove all numbers which are divisible by 2.
c) Find the next number, which is 3. Remove all numbers which are divisible by 3.
d) Next survivor is 5 and we repeat the same procedure.
e) For the given limit 25, we don't need to find anymore survivor after 5, as 5 X 5 = 25. In other words, we only process up to the square root of the limit.
 f) All survivor numbers in the array are Prime. We save those numbers in a separate array.



 For more clarification, please observe the illustration below:



I implemented the algorithm to find all prime numbers between 1 to 1000. Please note that, 1 is not considered as a prime number.

public class SieveOfEratosthenes {

 private final int LIMIT = 1000;
 private int[] flag = new int[LIMIT + 1];
 private int[] primes = new int[LIMIT];
 private int totalPrimes = 0;

 /**
  * Sieve Of Eratosthenes algorithm implementation
  * 
  * @return
  */
 public void implementSieve() {
  for (int i = 2; i * i <= LIMIT;) {
   for (int j = i + i; j <= LIMIT; j += i) {
    flag[j] = 1;
   }
   /* find the next prime */
   for (i = i + 1; flag[i] == 1 && i <= LIMIT; i++)
    ;
  }

  /* Save all primes */
  for (int i = 2; i <= LIMIT; i++) {
   if (flag[i] == 0) {
    primes[totalPrimes++] = i;
   }
  }
 }

 /**
  * Print all generated primes.
  * 
  * @return
  */
 public void printAllPrime() {
  for (int i = 0; i < this.totalPrimes; i++) {
   System.out.print(primes[i] + " ");
  }
 }

 public static void main(String args[]) {
  SieveOfEratosthenes eratosthenes = new SieveOfEratosthenes();
  eratosthenes.implementSieve();
  eratosthenes.printAllPrime();
 }

}

No comments:

Post a Comment