[Algorithm+Implementation] Sieve of Eratosthenes Algorithm for Finding all Prime Numbers Up To Any Given Limit

In mathematics, the sieve of Eratosthenes is an algorithm for finding all prime numbers up to any given limit.

It does so by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with the multiples of 2.

It works on the principle that all non-prime numbers are divisible by a prime number.

The sieve of Eratosthenes is one of the most efficient ways to find all of the smaller primes. It is named after Eratosthenes of Cyrene; the sieve was described and attributed to Eratosthenes in the Introduction to Arithmetic by Nicomachus.

 

Algorithm

Steps

  1. Initialize a boolean array of size max-size + 1 with true. 

    • We will need to find the prime including max-size. array[max-size] is in the location max-size + 1.

  2. Get every prime and cross off all multiples of it as false.

    • Cross off can start from the square(current prime) as all elements less than prime would have already crossed off.

    • We will have a count of elements that are crossed off and later we will create the primes array with this size.

      • The count is incremented only if this is the first time we are crossing off. For example, numbers such as 90 are multiples of both 2 and 3.

 

Implementation (Java)

Below is the static method that performs the algorithms:

public class SieveOfEratosthenes {

  // Implementation of Sieve Of Eratosthenes
  // that return a prime array
  static int[] sieveOfEratosthenes(int max) {
    boolean[] flags = new boolean[max + 1];

    initBooleanArray(flags, true);

    int primesCount = max + 1;

    int prime = 2;

    while (prime <= max) {
      int crossedOff = crossOff(flags, prime);

      primesCount = primesCount - crossedOff;

      prime = getNextPrime(flags, prime);

      if (prime >= flags.length)
        break;
    }

    // Copying primes to prime array
    int[] primes = new int[primesCount - 2];
    int count = 0;
    for (int i = 2; i <= max; i++) {
      if (flags[i]) {
        primes[count] = i;
        count++;
      }
    }

    // Returning primes array
    return primes;
  }

Above method used the below private methods:

  // Private method used by sieveOfEratosthenes
  // to cross off non-primes that are multiples of current prime
  private static int crossOff(boolean[] flags, int prime) {
    int crossedOff = 0;

    for (int i = prime * prime; i < flags.length; i = i + prime) {
      if (flags[i] != false) {
        flags[i] = false;
        // increment count only if this is the firt time
        // 90 may come twice as it is multiple of 2 and 3.
        crossedOff++;
      }

    }
    return crossedOff;
  }

  // Private method used by sieveOfEratosthenes
  // to get the next prime
  private static int getNextPrime(boolean[] flags, int current) {
    int next = current + 1;

    while (next < flags.length && flags[next] == false) {
      next++;
    }

    return next;
  }

Below is an utility method for initializing a boolean array:

  // Utility method for initializing a boolean array
  static void initBooleanArray(boolean[] arr, boolean value) {
    for (int i = 0; i < arr.length; i++) {
      arr[i] = value;
    }
  }

We can use the below test method (main method in this case) to test:

  // Test Method
  public static void main(String[] args) {
    int primes[] = sieveOfEratosthenes(1000);
    System.out.println("No of primes=" + primes.length);
    for (int i = 0; i < primes.length; i++) {
      System.out.print(primes[i] + " ");
    }

  }

}

Quick Notes Finder Tags

Activities (1) advanced java (1) agile (3) App Servers (6) archived notes (2) Arrays (1) Best Practices (12) Best Practices (Design) (3) Best Practices (Java) (7) Best Practices (Java EE) (1) BigData (3) Chars & Encodings (6) coding problems (2) Collections (15) contests (3) Core Java (All) (55) course plan (2) Database (12) Design patterns (8) dev tools (3) downloads (2) eclipse (9) Essentials (1) examples (14) Exception (1) Exceptions (4) Exercise (1) exercises (6) Getting Started (18) Groovy (2) hadoop (4) hibernate (77) hibernate interview questions (6) History (1) Hot book (5) http monitoring (2) Inheritance (4) intellij (1) java 8 notes (4) Java 9 (1) Java Concepts (7) Java Core (9) java ee exercises (1) java ee interview questions (2) Java Elements (16) Java Environment (1) Java Features (4) java interview points (4) java interview questions (4) javajee initiatives (1) javajee thoughts (3) Java Performance (6) Java Programmer 1 (11) Java Programmer 2 (7) Javascript Frameworks (1) Java SE Professional (1) JPA 1 - Module (6) JPA 1 - Modules (1) JSP (1) Legacy Java (1) linked list (3) maven (1) Multithreading (16) NFR (1) No SQL (1) Object Oriented (9) OCPJP (4) OCPWCD (1) OOAD (3) Operators (4) Overloading (2) Overriding (2) Overviews (1) policies (1) programming (1) Quartz Scheduler (1) Quizzes (17) RabbitMQ (1) references (2) restful web service (3) Searching (1) security (10) Servlets (8) Servlets and JSP (31) Site Usage Guidelines (1) Sorting (1) source code management (1) spring (4) spring boot (3) Spring Examples (1) Spring Features (1) spring jpa (1) Stack (1) Streams & IO (3) Strings (11) SW Developer Tools (2) testing (1) troubleshooting (1) user interface (1) vxml (8) web services (1) Web Technologies (1) Web Technology Books (1) youtube (1)