Java Program to find Prime Number with explanation

In this post, we will see how to find if the given number is Prime or not. Prime number are those numbers which cannot be divided by any number. 

For Example: 7 is a Prime Number because it is not divisible by 2 to 6. Similarly, 9 is a non-prime number as it is divisible by 3 

In this article, we will see three ways to find a number as Prime. From first to third program, you will find improvement in finding the prime number. The last program will be much better way (performance wise) to find Prime Number.

Program-I:

import java.util.Scanner;

public class Prime {

 public static void main(String[] args) {
  System.out.println("Enter number:");
   Scanner scanner = new Scanner(System. in); 
   String input = scanner. nextLine();
   int num = Integer.parseInt(input);
   boolean isPrime = true;
   for(int i = 2; i < num; i++) {
    isPrime = (num % i == 0)?false:true;
    if(isPrime == false) break;
   }
   if(isPrime)
    System.out.println("Number "+ input + " is a Prime number");
   else
    System.out.println("Number "+ input + " is a not Prime number");
 }
}

Output:

Run-1:
Enter number:
99
Number 99 is a not prime number
Run-2:
Enter number:
97
Number 97 is a prime number

Explanation:

In above code example, to find any number is prime or not, the code is using for loop start from 2 to that number and checking if any of the number is divisible by the given number or not. To check that we are checking if the remainder of the division is zero or not (num % i == 0).
% is the Java operator which returns the remainder of the divided number. If the number is divided and remainder is zero then the number is divisible by other number.

Program-II:

The second program is an improvement over the previous program. In this code example, we will check (if the input number is divisible) till half of that number. More information is provided in explanation section.

import java.util.Scanner;

public class Prime {

 public static void main(String[] args) {
  System.out.println("Enter number:");
   Scanner scanner = new Scanner(System. in); 
   String input = scanner. nextLine();
   int num = Integer.parseInt(input);
   boolean isPrime = true;
   for(int i = 2; i < num/2; i++) {
    isPrime = (num % i == 0)?false:true;
    if(isPrime == false) break;
   }
   if(isPrime)
    System.out.println("Number "+ input + " is a prime number");
   else
    System.out.println("Number "+ input + " is a not prime number");
 }
}

Output:

Run-1:
Enter number:
108
Number 108 is a not prime number
Run-2:
Enter number:
109
Number 109 is a prime number

Explanation:

In above code example, to find any number is prime or not, the code is using for loop start from 2 to the half of that  number. We don't need to check more as if the number is not divisible till half of that number, it will not be divisible by other half. For example to check prime number upto 100, we need to check till 50 because if the number is divisible by any number, its other divisible part will already been considered. 

Program-III:

import java.util.Scanner;

public class Prime {

 public static void main(String[] args) {
  System.out.println("Enter number:");
   Scanner scanner = new Scanner(System. in); 
   String input = scanner. nextLine();
   int num = Integer.parseInt(input);
   boolean isPrime = true;
   for(int i = 2; i < Math.sqrt(num); i++) {
    isPrime = (num % i == 0)?false:true;
    if(isPrime == false) break;
   }
   if(isPrime)
    System.out.println("Number "+ input + " is a prime number");
   else
    System.out.println("Number "+ input + " is a not prime number");
 }
}

Output:

Run-1:
Enter number:
105
Number 105 is a not prime number
Run-2:
Enter number:
101
Number 101 is a prime number

Explanation:

In above code example, to find any number is prime or not, the code is using for loop start from 2 to square root of that number and checking if any of the number is divisible by the given number or not. We don't need to check the complete squence, checking till its square root value is enough to say whether the number is prime or not. The reason is that if the number is non-prime, one of the divisible will fall within the square root of that number.

Among all this three examplex, Program-III is the best optimized one and is prefer to use it to find prime number.

That's all for this topic Java Program to find Prime Number. Please drop a comment if you have any doubt or suggestion. Thanks!