# Java Program to Check Prime Number

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.

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

Java program to print Fibonacci series up to N number

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.

Method 3 – Most efficient one

Subscribe Our Tutorials

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(n1/2)

Java Program to Check Prime Number

## 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.