Thursday, October 16, 2025

Binary Tree Traversal Using Breadth First Search Java Program

In this post we’ll see a Java program to do a Binary tree traversal using breadth first search which is also known as level order traversal of binary tree.

Breadth first search

Contrary to the depth first search where traversal is done by moving to node in the next level, in breadth first search all the nodes with in the same level are visited then only next level is visited.

For depth search Java program refer this post- Binary Tree Traversal Using Depth First Search Java Program

The level order traversal of the binary tree, in the above image will happen in the following order-

  1. Level 0 – 50
  2. Level 1- 30, 70
  3. Level 2- 15, 35, 62, 87
  4. Level 3- 7, 22, 31

Breadth first Java program for a binary tree can be written using both-

Breadth first search Recursive Java program

To write a Java program to recursively do a level order traversal of a binary tree you need to calculate height of the tree and then call method for level order traversal for level 0 to max level of the binary tree.

public void levelOrder(){
  int height = calculateTreeHeight(root);
  for(int i = 0; i < height; i++){
    levelOrderTraversal(root, i);
  }
}

// Method for breadth first search
public void levelOrderTraversal(Node node, int level){
  if(node == null){
    return;
  }
  if(level == 0){
    System.out.print(node.value + " ");
  }else{
    levelOrderTraversal(node.left, level-1);
    levelOrderTraversal(node.right, level-1);
  }    
}

Breadth first search Non-Recursive Java program

To write a Java program for level order traversal of a binary tree using an iterative method, a queue is used. Initially, root of the tree is inserted to the queue then you need to do the following until queue is empty.

  1. Poll a node from queue and display its value.
  2. Check if node has left child, if yes add that to the queue.
  3. Check if node has right child, if yes add that to the queue.

Iterative approach is considered more efficient than the recursive approach.

Binary Tree- Breadth first search Java program

Full Java program for breadth first search or level order traversal of binary tree.

import java.util.LinkedList;
import java.util.Queue;

public class BinaryTreeBFS {
  // first node
  private Node root;
  BinaryTreeBFS(){
    root = null;
  }
  // Class representing tree nodes
  static class Node{
    int value;
      Node left;
      Node right;
      Node(int value){
        this.value = value;
        left = null;
        right = null;        
      }
      public void displayData(){
        System.out.print(value + " ");
      }
  }
  
  public void insert(int i){
      root = insert(root, i);
  }
      
  //Inserting node to tree using recursion
  public Node insert(Node root, int value){
    if(root == null){
      return new Node(value);
    }
    // Move to the left if passed value is 
    // less than the current node
    if(value < root.value){
      root.left = insert(root.left, value);
    }
    // Move to the right if passed value is 
    // greater than the current node
    else if(value > root.value){
      root.right = insert(root.right, value);
    }
    
    return root;
  }
      
  // Method to get height of the tree
  public int calculateTreeHeight(Node root){
    if(root == null){
      return 0;
    }else{
      // height of left subtree
      int lsh = calculateTreeHeight(root.left);
      // height of right subtree
      int rsh = calculateTreeHeight(root.right);
      // height in each recursive call
      return Math.max(lsh, rsh) + 1;
    }        
  }
      
  public void levelOrder(){
    int height = calculateTreeHeight(root);
    for(int i = 0; i < height; i++){
      levelOrderTraversalRec(root, i);
    }
  }
    
  // Recursive Method for breadth first search
  public void levelOrderTraversalRec(Node root, int level){
      if(root == null){
        return;
      }
      if(level == 0){
        root.displayData();
      }else{
        levelOrderTraversalRec(root.left, level-1);
        levelOrderTraversalRec(root.right, level-1);
      }    
  }
  
  // Iterative Method for breadth first search
  public void levelOrderTraversalItr(Node root){
    if(root == null){
      return;
      }
      Queue<Node> queue = new LinkedList<Node>();
      queue.add(root);
      while(!queue.isEmpty()){
        Node node = queue.poll();
         node.displayData();
         if(node.left != null){
            queue.add(node.left);
         }
         if(node.right != null){
            queue.add(node.right);
         }
      }
  }
      
  public static void main(String[] args) {
    BinaryTreeBFS bst = new BinaryTreeBFS();
      bst.insert(50);
      bst.insert(70);    
      bst.insert(30);
      bst.insert(15);
      bst.insert(35);
      bst.insert(7);
      bst.insert(22);
      bst.insert(31);
      bst.insert(62);
      bst.insert(87);
      System.out.println("Tree Height- " + bst.calculateTreeHeight(bst.root));
      System.out.println("Level order traversal recursive");
      bst.levelOrder();
      System.out.println();
      System.out.println("Level order traversal iterative");
      bst.levelOrderTraversalItr(bst.root);
  }
}

Output

Tree Height- 4
Level order traversal recursive
50 30 70 15 35 62 87 7 22 31 
Level order traversal iterative
50 30 70 15 35 62 87 7 22 31 

Time and space complexity of binary tree level order traversal

With the recursive approach shown in this post which uses the height of the tree the time complexity in worst case is O(n2). Calculation of tree height is O(n) operation if tree is skewed (not well balanced).

For each level i, recursive method takes a top down approach traversing almost the whole tree to find nodes at level i. Which again is O(n) operation. So the total time complexity because of nested loop is O(n2).

Recursion depth is at most the height of the tree h. So the space complexity of recursive approach is O(h) where h may equal n in case of a skewed tree, for balanced tree h equals log(n).

With the iterative approach where Queue data structure is used the time complexity is O(n) as each tree node is visited exactly once.

Space complexity with iterative method is also O(n), as Queue may store upto n/2 elements in worst case.

That's all for this topic Binary Tree Traversal Using Breadth First Search Java Program. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Programs Page


Related Topics

  1. Find Minimum and Maximum Value Nodes in Binary Search Tree - Java Program
  2. Java Program to Add and Remove in Graph
  3. Counting Sort Program in Java
  4. Print Odd-Even Numbers Using Threads And wait-notify Java Program
  5. Find Duplicate Characters in a String With Repetition Count Java Program

You may also like-

  1. Zipping Files And Folders in Java
  2. Java Lambda Expression Comparator Example
  3. How to Convert String to Date in Java
  4. Matrix Subtraction Java Program
  5. Batch Processing in Java JDBC - Insert, Update Queries as a Batch
  6. PermGen Space Removal in Java 8
  7. String Comparison in Java equals(), compareTo(), startsWith() Methods
  8. How to Inject Null And Empty String Values in Spring

Java Program to Add and Remove in Graph

In this post we'll see how to write Java program for addition and removal from a graph data structure.

Addition and removal in a graph can be done in the following scenarios-

  1. Adding a vertex
  2. Adding an edge
  3. Removing a vertex
  4. Removing an edge

Another thing to consider while writing Java program for graph addition, removal is the representation of graph-

  1. Graph is represented using adjacency matrix
  2. Graph is represented using adjacency list

Please refer following posts to know more about graph representations- Graph Adjacency Representation - Java Program
Weighted Graph Adjacency Representation - Java Program

Graph addition removal Java program - Adjacency list representation

In the program, Map storing lists of its neighbours is used as adjacency list representation.

A separate class called Vertex is also there to encapsulate vertex information.

Adding a vertex means, adding that vertex as a key in the Map, along with a new ArrayList as a value.

Adding an edge means adding both the start vertex and the end vertex and the reverse link too if it is an undirected graph.

Removing a vertex means removing that particular key from the Map. Also remove where ever the removed vertex is listed as neighbour for other vertices.

Removing an edge means removing the link from starting point to end point, reverse link for the same vertices should also be removed for an undirected graph.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;

/**
 * Insert, delete in graph represented as adjacency list
 */
public class GraphDSAL {
  Map<Vertex, List<Vertex>> adjList = new HashMap<>();
  // Vertex class as nested class
  static class Vertex{
    String label;
    Vertex(String label){
      this.label = label;
    }
    public String getLabel() {
      return label;
    }
    public void setLabel(String label) {
      this.label = label;
    }
    @Override
    public int hashCode() {
      return Objects.hash(label);
    }
    @Override
    public boolean equals(Object obj) {
      if (this == obj)
        return true;
      if (obj == null)
        return false;
      if (getClass() != obj.getClass())
        return false;
      Vertex other = (Vertex) obj;
      return Objects.equals(label, other.label);
    }
    
  }
  
  public void addVertex(Vertex v) {
    adjList.putIfAbsent(v, new ArrayList<Vertex>());
  }
  
  public void removeVertex(Vertex v) {
    // remove vertex
    adjList.remove(v);
    // remove where ever the removed vertex is listed as neighbour
    adjList.values().forEach(e -> e.remove(v));
  }
  
  public void addEdge(String source, String destination) {
    Vertex vs = new Vertex(source);
      Vertex vd = new Vertex(destination);
    if(!adjList.containsKey(vs)) {
      addVertex(vs);
    }
    if(!adjList.containsKey(vd)) {
      addVertex(vd);
    }
    adjList.get(vs).add(vd);
    // Reverse link also required for undirected graph
    adjList.get(vd).add(vs);
  }
  
  public void removeEdge(String source, String destination) {
    Vertex vs = new Vertex(source);
      Vertex vd = new Vertex(destination);
      adjList.get(vs).remove(vd);
      // Reverse link removal also required for undirected graph
      adjList.get(vd).remove(vs);
  }
  // Method to display graph
  public void printGraph() {
    adjList.forEach((k, v) -> {
      System.out.print("Vertex " + k.getLabel() + " connects to ");
      v.forEach(e -> System.out.print(e.getLabel() + " "));
      System.out.println();
    });
  }

  public static void main(String[] args) {
    GraphDSAL graph = new GraphDSAL();
    graph.addVertex(new Vertex("A"));
    graph.addEdge("A", "B");
    graph.addEdge("A", "C");
    graph.addEdge("A", "E");
    graph.addEdge("C", "D");
    graph.addEdge("D", "E");
    
    graph.printGraph();
    
    graph.removeVertex(new Vertex("A"));
    //graph.removeEdge("A", "C");
    System.out.println("After removal");
    graph.printGraph();
        
  }

}

Output

Vertex A connects to B C E 
Vertex B connects to A 
Vertex C connects to A D 
Vertex D connects to C E 
Vertex E connects to A D 
After removal
Vertex B connects to 
Vertex C connects to D 
Vertex D connects to C E 
Vertex E connects to D 

Graph addition removal Java program - Adjacency matrix representation

When graph is represented as an adjacency matrix, that means using a 2-D array to represent a graph.

Adding a vertex means, incrementing the rows and columns of the adjacency matrix by 1 to accommodate new vertex. Copy the rows and columns from the old adjacency matrix to this new one and then assign the new adjacency matrix as the adjacency matrix of the graph.

Adding an edge means changing the row, column value to 1 for the array element, mapping to the start and end vertices for the added edge.

Removing a vertex means, decrementing the rows and columns of the adjacency matrix to represent removal of a vertex. While copying the rows and columns from the old adjacency matrix to this new one ensure that the values for the row and column represented by the removed vertex are not added to the new adjacency matrix. Assign the new adjacency matrix as the adjacency matrix of the graph.

Removing an edge means changing the row, column value to 0 for the array element, mapping to the start and end vertices for the removed edge.

/**
 * Insert, delete in graph represented as adjacency matrix
 */
public class GraphDSAM {
  private int vertices;
  private int[][] adjMatrix;
  
  GraphDSAM(int vertices){
    this.vertices = vertices;
    adjMatrix = new int[vertices][vertices];
  }
  
  public void addEdge(int source, int destination) {
    if((source < 0 || source >= vertices) || (destination < 0 || destination >= vertices)) {
      System.out.println("Invalid edge addition");
      return;
    }
    adjMatrix[source][destination] = 1;
    // For undirected graph reverse setting also required
    adjMatrix[destination][source] = 1;
  }
  
  public void removeEdge(int source, int destination) {
    if((source < 0 || source >= vertices) || (destination < 0 || destination >= vertices)) {
      System.out.println("Invalid edge removal");
      return;
    }
    adjMatrix[source][destination] = 0;
    // For undirected graph reverse setting also required
    adjMatrix[destination][source] = 0;
  }
  
  public void addVertex() {
    int changedSize = vertices + 1;
    int[][] changedAdjMatrix = new int[changedSize][changedSize];

    // Copy existing connections
    for (int i = 0; i < vertices; i++) {
      for (int j = 0; j < vertices; j++) {
        changedAdjMatrix[i][j] = adjMatrix[i][j];
      }
    }
    this.adjMatrix = changedAdjMatrix;
    vertices = changedSize;
  }
  
  public void removeVertex(int v) {
    if(v < 0 || v >= vertices){
      System.out.println("Invalid vertex removal");
      return;
    }
    int[][] changedAdjMatrix = new int[vertices-1][vertices-1];
    // maintaining row for changedAdjMatrix
    int tempRow = 0;
    
    for(int i = 0; i < adjMatrix.length; i++) {
      if(i == v) {
        continue;
      }
      // maintaining col for changedAdjMatrix
      int tempCol = 0;
      for(int j = 0; j < adjMatrix[0].length; j++) {
        if(j == v) {
          continue;
        }
        changedAdjMatrix[tempRow][tempCol] = adjMatrix[i][j];
        tempCol++;
      }
      tempRow++;
      
    }
    this.adjMatrix = changedAdjMatrix;
  }
  
  public void printGraph() {
    for(int i = 0; i < adjMatrix.length; i++) {
      for(int j = 0; j < adjMatrix[0].length; j++) {
        System.out.print(adjMatrix[i][j] + "\t");
      }
      System.out.println();
    }
  }
  
  public static void main(String[] args) {
    GraphDSAM graph = new GraphDSAM(5);
    graph.addEdge(0, 1);
    graph.addEdge(0, 2); 
    graph.addEdge(0, 4); 
    graph.addEdge(2, 3); 
    graph.addEdge(3, 4); 

    graph.printGraph();
    
    System.out.println("After adding a vertex");
    graph.addVertex();
    graph.addEdge(3, 5); 
    graph.printGraph();
    System.out.println("After removal");
    graph.removeEdge(3, 4);
    graph.printGraph();

  }

}

Output

0	1	1	0	1	
1	0	0	0	0	
1	0	0	1	0	
0	0	1	0	1	
1	0	0	1	0	
After adding a vertex
0	1	1	0	1	0	
1	0	0	0	0	0	
1	0	0	1	0	0	
0	0	1	0	1	1	
1	0	0	1	0	0	
0	0	0	1	0	0	
After removal
0	1	1	0	1	0	
1	0	0	0	0	0	
1	0	0	1	0	0	
0	0	1	0	0	1	
1	0	0	0	0	0	
0	0	0	1	0	0	

That's all for this topic Java Program to Add and Remove in Graph. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Programs Page


Related Topics

  1. Binary Tree Traversal Using Breadth First Search Java Program
  2. Binary Tree Traversal Using Depth First Search Java Program
  3. Binary Tree Implementation in Java - Insertion, Traversal And Search
  4. Sorted Linked List In Java
  5. Deque Implementation in Java Using Doubly Linked List

You may also like-

  1. Rabin-Karp Algorithm For Pattern Search - Java Program
  2. Two Sum - Elements in Array With Given Sum Java Program
  3. Java Program - Sieve of Sundaram to Find Prime Numbers
  4. How to Create Password Protected Zip File in Java
  5. Java CyclicBarrier With Examples
  6. static Reference to The Non-static Method or Field Error
  7. Difference Between @Controller And @RestController Annotations in Spring
  8. How to Create a Custom Structural Directive in Angular

Wednesday, October 15, 2025

Java Program to Check Prime Number

In this post we'll see a Java program to check whether given number is a prime number or not.

As we know that a number is a prime number if it is a natural number greater than 1 and it can be divided either by 1 or by the number itself. As example- 2, 3, 5, 7, 11, 13, 17 ….

First thing that may come to mind, while writing Java program for checking prime number, is to have a variable in a for loop that starts from 2 (as 1 will always divide the number) and increment it by one until it reaches the number that is checked for being prime number or not. In every iteration of the loop divide the number by variable, if remainder is zero at any time then the checked number is not a prime number.

That loop would look something like this-

for(int i = 2; i < num; i++){
  if(num % i == 0){
    flag = false;
    break;
  }
}

But that logic can be made more efficient. To check if a number is prime or not you need to run a loop starting from 2 till number/2 to check if number has any divisor.

For example, if number is 8 then you just need to check till 4 (8/2) to see if it divides by any number or not. Same way if you have a number 15 you just need to check till 7 to see if it divides completely by any number or not. We'll use the same logic to write our program to check for prime number.

Java program to check prime number or not

import java.util.Scanner;

public class PrimeCheck {
  public static void main(String[] args) {
    // take input from the user
    Scanner sc = new Scanner(System.in);
    System.out.println("Enter number: ");

    int num = sc.nextInt();
    boolean flag = isPrime(num);
    if(flag){
      System.out.println(num + " is a prime number.");
    }else{
      System.out.println(num + " is not a prime number.");
    }
  }
    
  private static boolean isPrime(int num){
    boolean flag = true;
    // loop from 2, increment it till number/2
    for(int i = 2; i <= num/2; i++){
      // no remainder, means divides 
      if(num % i == 0){
        flag = false;
        break;
      }
    }
    return flag;
  }
}

Output

Enter number: 
16
16 is not a prime number.

Enter number: 
31
31 is a prime number.

Here scanner class is used to get input from the user.

Refer How to Read Input From Console in Java to see other ways to get input from user.

That's all for this topic Java Program to Check Prime Number. If you have any doubt or any suggestions to make please drop a comment. Thanks!


Related Topics

  1. Java Program to Display Prime Numbers
  2. Java Program - Sieve of Eratosthenes to Find Prime Numbers
  3. Java Program - Sieve of Sundaram to Find Prime Numbers
  4. Armstrong Number or Not Java Program
  5. Fibonacci Series Program in Java

You may also like-

  1. Reading File in Java Using BufferedReader
  2. Count Number of Words in a String Java Program
  3. Abstraction in Java
  4. Inheritance in Java
  5. static Keyword in Java With Examples
  6. Difference Between ReentrantLock and Synchronized in Java
  7. Dependency Injection in Spring Framework
  8. Difference Between Checked And Unchecked Exceptions in Java

Java Program to Display Prime Numbers

This post shows a Java program to display prime numbers.

As we know that a number is a prime number if it is a natural number greater than 1 and it can be divided either by 1 or by the number itself. As example- 2, 3, 5, 7, 11, 13, 17 ….

To check if a number is prime or not you need to run a loop starting from 2 till number/2 to check if number has any divisor.

For example, if number is 8 then you just need to check till 4 (8/2) to see if it divides by any number or not. Same way if you have a number 15 you just need to check till 7 to see if it divides completely by any number or not. We'll use the same logic to write our program to display prime numbers up to the given upper range.

Looking for more efficient way to display prime numbers. Refer these sieving algorithms- Java Program - Sieve of Eratosthenes to Find Prime Numbers, Java Program - Sieve of Sundaram to Find Prime Numbers

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-

  1. 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.
  2. 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

  1. A boolean array of length (n-1)/2 is created with all elements as false initially.
  2. 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.
  3. 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

  1. Java Program - Sieve of Eratosthenes to Find Prime Numbers
  2. Fibonacci Series Program in Java
  3. Arrange Non-Negative Integers to Form Largest Number - Java Program
  4. Convert float to int in Java
  5. Binary Search Program in Java

You may also like-

  1. Insertion Sort Program in Java
  2. Check if Given String or Number is a Palindrome Java Program
  3. KMP Algorithm For Pattern Search - Java Program
  4. Difference Between Two Dates in Java
  5. Java Sealed Classes and Interfaces
  6. String Comparison in Java equals(), compareTo(), startsWith() Methods
  7. Comparing Two Strings in Python
  8. JavaScript filter Method With Examples

Monday, October 13, 2025

Java Programs

String

  1. Count Number of Words in a String Java Program
  2. Count Number of Times Each Character Appears in a String Java Program
  3. Check if Given String or Number is a Palindrome Java Program
  4. Java Program to Find The Longest Palindrome in a Given String
  5. How to Reverse a String in Java
  6. Reverse Each Word in a String Java Program
  7. Check Given Strings Anagram or Not Java Program
  8. Add Double Quotes to a String Java Program
  9. Split a String Java Program
  10. Find All Permutations of a Given String Java Program
  11. If Given String Sub-Sequence of Another String in Java
  12. Java Program to Find First Non-Repeated Character in a Given String
  13. Find The First Repeated Character in a String Java Program
  14. Find Duplicate Characters in a String With Repetition Count Java Program
  15. Convert String to int in Java
  16. Convert String to Byte Array Java Program
  17. Convert String to float in Java
  18. Convert String to double in Java
  19. Convert Char to String And String to Char in Java
  20. Convert String to Char Array in Java
  21. Removing Spaces Between Words in a String Java Program
  22. Manacher's Algorithm to Find The Longest Palindrome - Java Program
  23. Longest Prefix Suffix Java Program
  24. KMP Algorithm For Pattern Search - Java Program
  25. Rabin-Karp Algorithm For Pattern Search - Java Program
  26. Z Algorithm For Pattern Search - Java Program

Numbers

  1. Armstrong Number or Not Java Program
  2. Java Program to Reverse a Number
  3. Swap or Exchange Two Numbers Without Using Any Temporary Variable Java Program
  4. Java Program to Check Prime Number
  5. Java Program to Display Prime Numbers
  6. Java Program - Sieve of Eratosthenes to Find Prime Numbers
  7. Java Program - Sieve of Sundaram to Find Prime Numbers
  8. Greatest Common Divisor (GCD) of Two Numbers Java Program
  9. Least Common Multiple (LCM) of Two Numbers - Java Program
  10. Factorial Program in Java
  11. Fibonacci Series Program in Java
  12. Arrange Non-Negative Integers to Form Largest Number - Java Program
  13. How to Display Pyramid Patterns in Java - Part1
  14. How to Display Pyramid Patterns in Java - Part2
  15. Convert int to String in Java
  16. Convert float to String in Java
  17. Convert double to String in Java
  18. Convert float to int in Java
  19. Convert double to int in Java
  20. Convert Numbers to Words Java Program

Java - Array

  1. Find Duplicate Elements in an Array Java Program
  2. Remove Duplicate Elements From an Array in Java
  3. How to Remove Elements From an Array Java Program
  4. How to How to Find Common Elements Between Two Arrays Java Program
  5. Find Largest and Second Largest Number in Given Array Java Program
  6. Find Largest And Smallest Number in a Given Array Java Program
  7. Array Rotation Java Program
  8. Matrix Multiplication Java Program
  9. Matrix Addition Java Program
  10. Matrix Subtraction Java Program
  11. Find Maximum And Minimum Numbers in a Given Matrix Java Program
  12. Find The Maximum Element in Each Row of a Matrix Java Program
  13. Two Sum - Array Indices With Given Sum Java Program
  14. Two Sum - Elements in Array With Given Sum Java Program

Java Date&Time

  1. Format Date in Java Using SimpleDateFormat
  2. How to Convert Date to String in Java
  3. How to Convert String to Date in Java
  4. How to Convert Date And Time Between Different Time-Zones in Java
  5. How to Display Time in AM-PM Format in Java
  6. Display Time in 24 Hours Format in Java
  7. Difference Between Two Dates in Java
  8. Compare Dates in Java
  9. Create Date Object in Java With Date and Time Values
  10. Java Program to Get Current Date and Time

Java - Collections

  1. How to Iterate a HashMap of ArrayLists of String in Java
  2. How to Sort Elements in Different Order in Java TreeSet

Lambda Expression

  1. Java Lambda Expression Runnable Example
  2. Java Lambda Expression Comparator Example
  3. Java Lambda Expression Callable Example

Java Internals

  1. How to Compile Java Program at Runtime
  2. How to Run javap Programmatically From Java Program
  3. Running Dos/Windows Commands From Java Program
  4. How to Run a Shell Script From Java Program

Data Structures in Java

  1. Linked List Implementation Java Program
  2. Stack Implementation in Java Using Array
  3. Stack Implementation in Java Using Linked List
  4. Queue Implementation in Java Using Array
  5. Queue Implementation in Java Using Linked List
  6. Java Program to Detect And Remove Loop in a Linked List
  7. How to Reverse a Linked List in Java
  8. Sorted Linked List In Java
  9. Doubly Linked List Implementation Java Program
  10. Deque Implementation in Java Using Doubly Linked List
  11. How to Reverse a Doubly Linked List in Java
  12. Binary Tree Implementation in Java - Insertion, Traversal And Search
  13. Java Program to Delete a Node From Binary Search Tree (BST)
  14. Find Minimum and Maximum Value Nodes in Binary Search Tree - Java Program
  15. Binary Tree Traversal Using Breadth First Search Java Program
  16. Binary Tree Traversal Using Depth First Search Java Program
  17. Graph Adjacency Representation - Java Program
  18. Weighted Graph Adjacency Representation - Java Program
  19. Java Program to Add and Remove in Graph

Java I/O

  1. Reading File in Java Using BufferedReader
  2. Reading File in Java Using Scanner
  3. Reading Delimited File in Java Using Scanner
  4. Reading File in Java Using Files.lines And Files.newBufferedReader
  5. How to Read File From The Last Line in Java
  6. How to Read Properties File in Java
  7. How to Read Input From Console in Java
  8. Read File Asynchronously Java Program
  9. Write to a File in Java
  10. Writing a File Asynchronously Java Program
  11. How to Append to a File in Java
  12. Read or List All Files in a Folder in Java
  13. Java Program to Delete File And Directory Recursively
  14. How to Find Last Modified Date of a File in Java
  15. How to Count Lines in a File in Java
  16. Java Program to Print Line Numbers With Lines in Java
  17. Java Program to Convert a File to Byte Array
  18. How to Read Excel File in Java Using Apache POI
  19. How to Write Excel File in Java Using Apache POI
  20. Creating Temporary File in Java

Compressing & Decompressing Files

  1. Zipping Files And Folders in Java
  2. Unzip File in Java
  3. How to Create Password Protected Zip File in Java
  4. Compress And Decompress File Using GZIP Format in Java
  5. Creating Tar File And GZipping Multiple Files in Java
  6. How to Untar a File in Java

Java Multi-Threading

  1. Print Odd-Even Numbers Using Threads And wait-notify Java Program
  2. Print Odd-Even Numbers Using Threads And Semaphore Java Program
  3. Producer-Consumer Java Program Using wait notify
  4. Producer-Consumer Java Program Using ArrayBlockingQueue
  5. Producer-Consumer Java Program Using volatile
  6. How to Run Threads in Sequence in Java
  7. Printing Numbers in Sequence Using Threads Java Program
  8. How to Create Deadlock in Java
  9. Setting And Getting Thread Name And Thread ID in Java
  10. Java Program to Create Your Own BlockingQueue

Java XML

  1. How to Create PDF From XML Using Apache FOP

PDF Generation in Java

  1. Creating PDF in Java Using iText
  2. How to Create PDF in Java Using OpenPDF
  3. Creating PDF in Java Using Apache PDFBox
  4. HTML to PDF in Java + Flying Saucer and OpenPDF
  5. Convert HTML to PDF in Java + Openhtmltopdf and PDFBox

Enum

  1. Comparing Enum to String in Java
  2. Converting String to Enum Type in Java
  3. Converting Enum to String in Java

Java Reflection

  1. Generating Getters And Setters Using Reflection in Java
  2. Invoking Getters And Setters Using Reflection in Java

JDBC Programs

  1. Connection Pooling Using Apache DBCP in Java
  2. Connection Pooling Using C3P0 in Java
  3. Java Program to Get All DB Schemas
  4. Java Program to Get All The Tables in a DB Schema

Sorting Algorithms in Java

  1. What is In-place Algorithm
  2. Bubble Sort Program in Java
  3. Selection Sort Program in Java
  4. Insertion Sort Program in Java
  5. Shell Sort Program in Java
  6. Merge Sort Program in Java
  7. Quick Sort Program in Java
  8. Heap Sort Program in Java
  9. Tree Sort in Java Using Binary Search Tree
  10. Counting Sort Program in Java
  11. Bucket Sort Program in Java
  12. Radix Sort Program in Java

Searching Algorithms in Java

  1. Linear Search (Sequential Search) Java Program
  2. Binary Search Program in Java
  3. Ternary Search Program in Java
  4. Interpolation Search Program in Java
  5. Exponential Search Program in Java

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-

Sieve of Eratosthenes

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

Java Program - Sieve of Eratosthenes

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

  1. Java Program to Check Prime Number
  2. Greatest Common Divisor (GCD) of Two Numbers Java Program
  3. Least Common Multiple (LCM) of Two Numbers - Java Program
  4. Convert float to String in Java

You may also like-

  1. Weighted Graph Adjacency Representation - Java Program
  2. Find Maximum And Minimum Numbers in a Given Matrix Java Program
  3. Two Sum - Elements in Array With Given Sum Java Program
  4. Manacher's Algorithm to Find The Longest Palindrome - Java Program
  5. Optional Class in Java With Examples
  6. finally Block in Java Exception Handling
  7. Spring Transaction Management Example - @Transactional Annotation and JDBC
  8. Angular HttpClient - Set Response Type as Text