A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself.

Prime numbers has many applications in computer science particularly in cryptography. It’s also important from the examination perspective because lots of problems can be created based on the concept of prime numbers.

In this post I would like to discuss about the method commonly used by students of ICSE/ISC to test for primality and how it can be improvised. The most basic method for primality uses trial division as follows:

class Prime{
    public static boolean isPrime(int number){
        for(int i=1; i<=number; i++){
            if(number%i==0){
                factorCount++;
            }
        }
        if(factorCount==2) return true;
        else return false;
    }
    public static void main(String args[]){
        System.out.println("Test cases for primality");
        System.out.println("-1\t:"+isPrime(-1));
        System.out.println("1\t:"+isPrime(1));
        System.out.println("2\t:"+isPrime(2));
        System.out.println("3\t:"+isPrime(3));
        System.out.println("4\t:"+isPrime(4));
        System.out.println("15\t:"+isPrime(15));
        System.out.println("113\t:"+isPrime(113));
    }
}

The above solution will give correct results but is very slow especially for large numbers. The trial division logic can be improved if we take the following into account:

1. Integers less than 2 cannot be prime by definition.
2. Two is the only even integer which is prime. This also means that there is no need to check for divisibility by even integers because odd numbers are not divisible by even numbers.

If we incorporate the above points into out program we will get the following:

class Prime{
    public static boolean isPrime(int number){
        if(number<2) return false;
        else if(number==2) return true;
        else if(number%2==0) return false;
        else{
            for(int i=3; i<number;i+=2){
                if(number%i==0){
                    return false;
                }
            }
        }
        return true;
    }

    public static void main(String args[]){
        System.out.println("Test cases for primality");
        System.out.println("-1\t:"+isPrime(-1));
        System.out.println("1\t:"+isPrime(1));
        System.out.println("2\t:"+isPrime(2));
        System.out.println("3\t:"+isPrime(3));
        System.out.println("4\t:"+isPrime(4));
        System.out.println("15\t:"+isPrime(15));
        System.out.println("113\t:"+isPrime(113));
    }
}

Note that now the loop is starting from 3 and going up to one less than the number. We are not starting from one and we are not going up to the number. If any factor of number is found it’s the third factor and hence number is not prime.

The program can be further improved if we consider the fact that factors are always in pairs. For example let’s see the factors of 100:
1 x 100 =100
2 x 50 = 100
4 x 25 = 100
5 x 20 = 100
10 x 10 = 100
20 x 5 = 100
25 x 4 = 100
50 x 2 = 100
100 x 1 = 100
Notice that there is repetition of factors after the square root of the number (i.e. √100 = 10) meaning 1 x 100 = 100 x 1, 2 x 50 = 50 x 2, 4 x 25 = 25 x 4 and so on. We can have some more  improvement in the performance if we take this repetition into account. So the final program for the primality test is as follows:

class Prime{
    public static boolean isPrime(int number){
        if(number<2) return false;
        else if(number==2) return true;
        else if(number%2==0) return false;
        else{
            int limit = (int)Math.sqrt(number);
            for(int i=3; i<=limit;i+=2){
                if(number%i==0){
                    return false;
                }
            }
        }
        return true;
    }

    public static void main(String args[]){
        System.out.println("Test cases for primality");
        System.out.println("-1\t:"+isPrime(-1));
        System.out.println("1\t:"+isPrime(1));
        System.out.println("2\t:"+isPrime(2));
        System.out.println("3\t:"+isPrime(3));
        System.out.println("4\t:"+isPrime(4));
        System.out.println("15\t:"+isPrime(15));
        System.out.println("113\t:"+isPrime(113));
    }
}

Note: Click here to see how to time the above methods.