Write a Java program to check prime number. Given an input integer, We have to write an efficient code to check whether a number is prime or not.

Before writing a program, let’s quickly understand what is a prime number.

### Prime Number

A prime number is a number that is greater than 1 and it has no positive divisors other than 1 and itself.

For example – 3, 13, 7 is a prime number, as it’s divisible by 1 and itself. Similarly, 29, 19 etc. are also prime numbers.

6 is not a prime number as it’s divisible by 1, 2, 3 and 6.

2 is the only even prime number.

## How to check whether a number is prime or not in Java

There are multiple approaches through which we can check whether a number is prime or not.

C program to check whether a number is prime or not

** Method 1 **

It is the simplest approach to check whether a number is prime or not. In this approach, we run a loop from 2 to n-1 (where n is an input number) and check whether a number is perfectly divisible by any other number other than 1 and itself. If a number is divisible (other than 1 and itself) then it’s not a prime number.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | //check whether a number is prime or not public static boolean checkPrime(int n) { /* If n is less than or equal to 1, then it's not a prime */ if(n <= 1) { return false; } //Run a loop from 2 to n-1 for( i = 2; i < n; i++) { /*If n is divisible by any other number other than 1 and itself, *then it's not a prime number */ if(n%i == 0){ return false; } } return true; } |

The time complexity of this approach is O(n).

Java program to print Fibonacci series up to N number

Programming questions on linked list

**Method 2 ** –

Let’s improve a method 1. Instead of running a loop from 2 to n-1. We can run a loop to from 2 to n/2.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | //check whether a number is prime or not public static boolean checkPrime(int n) { if(n <= 1) { return false; } //Run a loop from 2 to n-1 for( i = 2; i <= n/2; i++) { if(n%i == 0){ return false; } } return true; } |

**Method 3 – Most efficient one**

In this approach, we run a loop from 2 to sqrt(n).

### Why do we check up to the square root of n to determine whether a number is prime or not?

To understand this concept, let’s take a number n and suppose the value of n is 15. 15 is not a prime number. So the factors of 15 are 3 and 5. The Square root of sqrt(15) is 3.87.

If a number n is not a prime, it can be factored into two factors a and b:

n = a*b

If both the factors a and b is greater than the square root of n. Then the a*b would be greater than n. So at least one of those factors must be less than or equal to the square root of n. To check if a number n is prime, we only need to test for factors less than or equal to the square root.

The time complexity of this approach is O(n^{1/2})

## Java Program to Check Prime Number

We have compared three approaches and their time complexities. Let’s write a java code to check prime number.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | import java.io.*; import java.math.*; public class Solution { public static boolean checkPrime(int n) { /* Run a loop from 2 to sqrt(n) */ for (int i=2; i <= Math.sqrt(n); i++) { /* Check if it is divisible */ if(n%i == 0){ return false; } } return true; } public static void main(String[] args) { System.out.println("Enter a number \n"); Scanner in = new Scanner(System.in); int n = in.nextInt(); if(n>=2 && checkPrime(n)){ System.out.println("Prime"); } else { System.out.println("Not prime"); } } } |