How to determine a prime number efficiently?

Learn about an efficient algorithm to determine a given number is prime or not. Also learn to implement prime number algorithm in Java 8 program.

1. Prime Number

A prime number is a natural number greater than 1 that cannot be formed by multiplying two smaller natural numbers other than 1.

In other words, a prime number (P) is a number greater than 1 whose only factors are 1 and the number (P) itself.

For example, 3 is a prime number because it can be divided only by 1 and 3 (itself). However, 4 is NOT prime number because it can be divided by 2 i.e. it can be written as 2 x 2.

There are infinitely many prime numbers. Another way of saying this is that the sequence '2, 3, 5, 7, 11, 13, ...' of prime numbers never ends.

2. Algorithm to calculate prime number

Please note that there is no known efficient formula (mathematically proven) to determine a number is prime or not.

Generally, we can determine a number is prime or not in below steps:

1. 2 is only prime number which is also even number. So, if given number N is 2 the it is PRIME number.
2. If given number N is even number then it is NOT PRIME number.
3. Find out square root on N. Traverse all odd numbers up to the sqrt(N) and try to devide the N with current odd number. If remainder is 0 for any odd number then number is NOT PRIME.
4. Else – number is PRIME.

boolean isPrime(int number) 
{
	if(number <= 2)
		return number == 2;
	else
		return  (number % 2) != 0 
				&&
				IntStream.rangeClosed(3, (int) Math.sqrt(number))
				.filter(n -> n % 2 != 0)
		        .noneMatch(n -> (number % n == 0));
}

3. Java program to determine a prime number

Let’s implement above prime number algorithm in Java 8. We have used IntStream which helps in generating a sequence of integers supporting sequential and parallel aggregate operations.

package com.howtodoinjava.example;

import java.util.stream.IntStream;

public class Main 
{
	public static void main(String[] args) 
	{
		System.out.println("2 is prime number :: " + isPrime(2));
		System.out.println("3 is prime number :: " + isPrime(3));
		System.out.println("4 is prime number :: " + isPrime(4));
		System.out.println("5 is prime number :: " + isPrime(5));
		System.out.println("6 is prime number :: " + isPrime(6));
		System.out.println("7 is prime number :: " + isPrime(7));
		System.out.println("8 is prime number :: " + isPrime(8));
		System.out.println("9 is prime number :: " + isPrime(9));
		System.out.println("10 is prime number :: " + isPrime(10));
		System.out.println("11 is prime number :: " + isPrime(11));
	}
	
	static boolean isPrime(int number) {
		if(number <= 2)
			return number == 2;
		else
			return  (number % 2) != 0 
					&&
					IntStream.rangeClosed(3, (int) Math.sqrt(number))
					.filter(n -> n % 2 != 0)
			        .noneMatch(n -> (number % n == 0));
	}
}

Program output.

2 is prime number :: true
3 is prime number :: true
4 is prime number :: false
5 is prime number :: true
6 is prime number :: false
7 is prime number :: true
8 is prime number :: false
9 is prime number :: false
10 is prime number :: false
11 is prime number :: true

Drop me your questions related to how to determine a given number is prime in Java.

Happy Learning !!

References:

Wikipedia
IntStream Java Docs