Skip to main content

ProwessApps

Learn · Practice · Excel
About Contact
Login / Register

Java Program to check the given number is prime or not.

Java Code Example — Simple Programs

ADVERTISEMENT

Java Program to check the given number is prime or not.

Objective

Write a Java program to determine whether a given positive integer is a prime number.

Algorithm / Approach

  1. Read an integer n from the user.
  2. Initialize a flag variable to 0.
  3. Run a loop from i = 2 up to the square root of n.
  4. Inside the loop, check if n is perfectly divisible by i (n % i == 0).
  5. If divisible, set flag = 1 and immediately break out of the loop.
  6. After the loop, if flag == 0, the number is prime; otherwise, it is not prime.
Test.java 
import java.util.Scanner;
class Test {
 public static void main(String[] a)
 {
  Scanner s=new Scanner(System.in);
  System.out.print("Enter a num: ");
  int n = s.nextInt();
  int flag = 0;
  for(int i =2; i<=Math.sqrt(n);i++){
   if(n%i==0) {
    flag = 1;
    break;
   }
  }
  if(flag==0) {
   System.out.print(n+" is a prime no.");
  }
  else {
   System.out.print(n+" is not a prime no.");
  }
 }
}

Expected Output

Enter a num: 45
45 is not a prime no.

Explanation of the Program

  • A prime number is only divisible by 1 and itself.
  • Instead of checking all numbers up to n-1, the program optimizes the search by only checking up to Math.sqrt(n). If a number has factors, at least one factor must be less than or equal to its square root.
  • The flag variable acts as a boolean indicator. Once a divisor is found, the break statement stops further unnecessary checks.

Complexity

Time Complexity O(&radic;n) - Optimized by stopping at the square root.
Space Complexity O(1)

Common Mistakes

  • Checking divisibility up to n instead of the square root, which is highly inefficient for very large numbers.
  • Not handling edge cases like negative numbers, 0, or 1 (which are not prime).
ADVERTISEMENT