The Sieve Algorithm in Java: A Detailed and Simple Explanation with Examples

The Sieve of Eratosthenes is an ancient and efficient algorithm for finding all prime numbers up to a specified limit. It eliminates the need for repeated divisions or trial division methods, making it an excellent choice for prime number generation. In the below steps, we will delve into the world of the Sieve algorithm, exploring its core principles, providing detailed examples of its implementation in Java, and analyzing its time and space complexity.

  1. Understanding the Sieve Algorithm:

The Sieve algorithm works on the principle of iteratively sieving out composite numbers to reveal the prime numbers. It starts with a list of numbers from 2 up to the desired limit and progressively removes multiples of each prime number found, leaving only the primes behind.

  1. Implementation of the Sieve Algorithm in Java:

To implement the Sieve algorithm in Java, we can follow these steps:

Step 1: Create a boolean array to represent the numbers from 2 up to the desired limit. By default, assume all numbers are prime.

Example:

int limit = 100;
boolean[] isPrime = new boolean[limit + 1];
Arrays.fill(isPrime, true);

Step 2: Iterate through the numbers starting from 2 and mark all multiples of each prime number as composite.

Example:

for (int i = 2; i * i <= limit; i++) {
    if (isPrime[i]) {
        for (int j = i * i; j <= limit; j += i) {
            isPrime[j] = false;
        }
    }
}

Step 3: Collect all the prime numbers into a list or perform any desired operation with them.

Example:

List<Integer> primes = new ArrayList<>();
for (int i = 2; i <= limit; i++) {
    if (isPrime[i]) {
        primes.add(i);
    }
}
  1. Example Usage and Output:

Let’s consider an example where we want to find all prime numbers up to the limit of 30 using the Sieve algorithm.

Example:

int limit = 30;
boolean[] isPrime = new boolean[limit + 1];
Arrays.fill(isPrime, true);

for (int i = 2; i * i <= limit; i++) {
    if (isPrime[i]) {
        for (int j = i * i; j <= limit; j += i) {
            isPrime[j] = false;
        }
    }
}

List<Integer> primes = new ArrayList<>();
for (int i = 2; i <= limit; i++) {
    if (isPrime[i]) {
        primes.add(i);
    }
}

System.out.println(primes); // Output: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

The output shows all the prime numbers within the specified limit of 30.

  1. Time and Space Complexity Analysis:

The Sieve algorithm offers an efficient way to generate prime numbers. Let’s analyze its time and space complexity:

  • Time Complexity: The Sieve algorithm has a time complexity of O(n log log n), where n is the given limit. This is because each number is marked as composite only once when its multiples are eliminated.
  • Space Complexity: The Sieve algorithm requires a boolean array of size n+1 to store the prime flags. Hence, the space complexity is O(n).

The Sieve algorithm is a powerful and efficient method for generating prime numbers. By iteratively sieving out composite numbers, it reveals only the prime numbers within a given limit. Understanding the core principles, implementing the Sieve algorithm in Java, and analyzing its time and space complexity allows you to efficiently generate prime numbers for various applications. Embrace the simplicity and effectiveness of the Sieve algorithm in your Java projects and explore its applications in number theory, cryptography, and other fields.

Leave a Comment

Your email address will not be published. Required fields are marked *

Scroll to Top