Java Program - Sieve of Sundaram to Find Prime Numbers

In this post we'll see how to write a program in Java to find prime numbers up to the given limit using Sieve of Sundaram algorithm.

Sieve of Sundaram algorithm

Sieve of Sundaram algorithm takes only odd numbers into consideration, completely eliminating even numbers from the beginning itself.

Two main points about the algorithm are-

Let’s say we need prime number with in the range 0..n. Every odd number with in this range can be expressed as 2x+1, where x lies between 0 to n. So, to get odd numbers between 0..n we need to run loop till (n - 1)/2 only.
For example, if you need all the prime number in the range 1 to 50 then you need to run the loop till (50 – 1)/2 = 24.5 which can be taken as 24. With that 2x+1 gives us 2 * 24 + 1= 49 which is the last odd number with in the range.
Note that there is only one even prime number which is 2, that is why this algorithm takes that as a special case and concentrates only on odd numbers.
In order to eliminate odd numbers which are not prime numbers x = i + j + 2ij equation is used.

How does sieve of Sundaram algorithm work

A boolean array of length (n-1)/2 is created with all elements as false initially.
With in the nested loops, mark the elements with indices of the form i + j + 2ij as true. This process eliminates all the odd composite numbers.
Then you are left with only those elements, still marked as false in the array, which are prime numbers and of the form 2i+1.

Sieve of Sundaram Java program

public class SieveOfSundaram {
  private static void getPrimes(int n) {
  int limit = (n - 1) / 2;
  boolean[] marked = new boolean[limit + 1];

  // Mark all numbers of the form i + j + 2ij as true 
  // where 1 <= i <= j
  for (int i = 1; i <= limit; i++) {
    for (int j = i; (i + j + 2 * i * j) <= limit; j++) {
      marked[i + j + 2 * i * j] = true;
    }
  }

  // print even prime number
  if (n >= 2)
    System.out.print(2 + " ");
  // Print rest of the prime numbers with in the limit
  for (int i = 1; i <= limit; i++)
    if (marked[i] == false)
      System.out.print(2 * i + 1 + " ");

  }
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    System.out.println("Enter the number for range: ");
    int n = sc.nextInt();
    getPrimes(n);
    sc.close();

  }
}

Output

Enter the number for range: 
50
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

Explanation for the equation

You can verify that equation i+j+2ij maps to odd composite numbers, let's take n = 25 then the limit is 12.

With in this nested loop-

for (int i = 1; i <= limit; i++) {
  for (int j = i; (i + j + 2 * i * j) <= limit; j++) {
    marked[i + j + 2 * i * j] = true;
  }
}

When i = 1, j = 1, i+j+2ij = 4 so 2i+1 is 9 which is an odd composite number. 
i=1, j=2, then i+j+2ij = 7 so 2i+1 is 15 which is an odd composite number. 
i=1, j=3 then i+j+2ij = 10 so 2i+1 is 21 which is an odd composite number. 
Then i becomes 2, 
i=2, j=2 then i+j+2ij = 12 so 2i+1 is 25 which is an odd composite number.

That's what this nested loop achieves by marking elements in the array.

Time and space complexity of Sieve of Sundaram algorithm

The time complexity of Sieve of Sundaram algorithm is O(n log n). The outer loop runs (n-1)/2 times which can be taken as O(n). The inner loop runs in logarithmic time as the number of iterations required to complete the loop keeps on decreasing.

A Boolean array of size (n - 1)/2 + 1 is required so the space complexity is O(n).

That's all for this topic Java Program - Sieve of Sundaram to Find Prime Numbers. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Advanced Tutorial Page

Related Topics

You may also like-

Tech Tutorials

Wednesday, October 15, 2025