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:

- Integers less than 2 cannot be prime by definition.
- 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.

Mohit NandaWhat would be even more interesting to see, would be, a small benchmark to compare the time across the 3 methods for say doing it for the first 1,000,000 numbers.

Vinay SinghPost authorNice suggestion Mohit. I shall be doing the same in my next post. Thank you for the suggestion. 🙂

Pingback: Composite Magical Number | VinaySingh.info

Pingback: Timing methods in Java for profiling using System.nanoTime()

Pingback: Smith number | www.VinaySingh.info

Pingback: Twin prime | www.VinaySingh.info

Pingback: Recursive primality test | www.VinaySingh.info

Pingback: Circular Prime - Solution of ISC Computer Practical 2016 - www.VinaySingh.info