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!

Do you have a question on the above article or do you have a programming problem that you are unable to solve? Please email us.

Comments are closed.