Java Program - Sieve of Eratosthenes 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 Eratosthenes algorithm.

Sieve of Eratosthenes algorithm

Sieve of Eratosthenes algorithm work by creating an array of n+1 size if the prime numbers are to be listed for range 1..n.

For each prime number mark all its multiple as non-prime in the table. That's what make this algorithm efficient, for example if 2 is a prime number then none of its multiple 4, 6, 8… is going to be a prime number. Same way if 3 is a prime number then none of its multiple 6, 9, 12, 15.. is going to be a prime number.

After the marking is done, which ever numbers are still unmarked are prime numbers.

For example, if we have to find prime numbers in the range 1-10 then we can visualize it as given here-

For 2, mark all the multiples of 2 as not prime-

For 3, mark all the multiples of 3 as not prime-

Same way for next numbers 5 and 7. At the end you will be left with the numbers that are prime. Note, that 1 is also not considered as a prime number that will be taken care of in the program by starting the loop from 2.

Sieve of Eratosthenes Java program

import java.util.Arrays;
import java.util.Scanner;

public class EratosthenesSieve {
  private static void getPrimes(int n) {
    // table to keep track of prime or not
    boolean[] primeTable = new boolean[n+1];
    // intially mark all of the array element as true
    Arrays.fill(primeTable, true);
    for(int i = 2; i <= n; i++) {
      // still true means it is a prime number
      if(primeTable[i]) {
        // multiples of i should be marked as not prime
        for(int j = i * i; j <= n; j = j+i) {
          primeTable[j] = false;
        }
      }
    }
    // print all the prime numbers which'll be the 
    // the elements in the array still marked as true
    // printing can also be done in the above for loop itself
    // after the if condition block
    for(int i = 2; i <= n; i++) {
      if(primeTable[i]) {
        System.out.print(i + " ");
      }
    }
  }

  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

Time and space complexity of Sieve of Eratosthenes algorithm

Outer loop runs n times.

Inner loop runs n/i times for i = 2, 3, 5…. when i = 2, the internal loop will be executed n/2 times. For i = 3, it'll be executed n/3 times. For i = 5, it'll be executed n/5 times, and so on. This results in the time complexity of O(log(log n))

Thus, the overall time complexity is O(n X log(log n))

We need an array of length n+1 for marking the non-primes so the space complexity is O(n).

That's all for this topic Java Program - Sieve of Eratosthenes 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

Monday, October 13, 2025