# Prime Number Checker in Java Using Trial Division

A prime number is a natural number which can only be divided(without leaving a remainder) by 1 and the number itself. For example, number 5 is a prime number since it can be divided by 1 and 5. Number 6 is not a prime since it can be divided by 2 and 3 without leaving a reminder!

One of the easiest ways to check whether a number is a prime or not is to use trial division. In this method we will divide the number by consecutive natural numbers starting with 2 and ending at (number – 1). If we are able to divide it by a number without leaving a remainder, we know that the number is not prime.

However for a number n, we don’t need to do trial division till (n-1). We only need to check for prime up to square root of n. This is because if n = a * b, **both** a and b cannot be greater than square root of n!

## Check Prime Number in Java

The following Java program uses trial division up to square root of **n** to check whether **n** is a prime. This program may take forever to execute for very large numbers!,

public class PrimeNumberChecker { public static void main(String[] args) { long number = 98764321261L; long sqr_root = (long)Math.sqrt(number); for (long i = 2; i <= sqr_root; i++) { if (number % i == 0) { System.out.println(number+" is NOT prime. It is found to be a product of "+i+" and "+number/i); return; // don't process anything } } System.out.println(number+" is a prime number!"); } }

Note that for very large numbers, this is method is very slow since it has do a large number of mathematical operations. For the prime number 9876432123444371, the above program took about one second and for the prime number 987643212344434391 it took over 10 seconds!