Check If A Number Is Prime

This recipe shows how to check if a given number is prime. We will demonstrate two different approaches to implementing the solution.

Problem:

Given a number, check if it is a prime number.

Analysis:

As described on Wikipedia, a prime number is a natural number greater than 1 that is not a product of two smaller natural numbers.

For example, the first few prime numbers are:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53

Solution 1:

The first solution is fast and uses the following facts:

Wikipedia describes this algorithm in more detail.

public class Prime1 {

    private static boolean isPrime(int number) {
        // special case: for numbers 3 and under, only 2 and 3 are prime
        if (number <= 3) {
            return number > 1;
        }
        // all primes greater than 3 are of the form 6k[+/-]1;
        // eliminate numbers divisible by 2 or 3
        if ((number % 2 == 0) || (number % 3 == 0)) {
            return false;
        }
        // and only check for divisors up to sqrt(number)
        for (int i = 5; i * i <= number; i += 6) {
            if ((number % i == 0) || ((number % (i + 2)) == 0)) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        final int number = Integer.parseInt(args[0]);
        System.out.println(isPrime(number));
    }
}

Link To: Java Source Code

Solution 2:

The next solution is simpler but less optimized. It uses the following facts:

public class Prime2 {

    private static boolean isPrime(int number) {
        // special case: for numbers 2 and under, only 2 is prime
        if (number <= 2) {
            return number > 1;
        }
        // eliminate even numbers which are not prime
        if (number % 2 == 0) {
            return false;
        }
        // only check odd numbers for prime, and
        // only check for divisors up to sqrt(number)
        for (int i = 3; i * i <= number; i += 2) {
            if (number % i == 0) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        final int number = Integer.parseInt(args[0]);
        System.out.println(isPrime(number));
    }
}

Link To: Java Source Code