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!