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:

- 2 is only prime number which is also even number. So, if given number N is 2 the it is PRIME number.
- If given number N is even number then it is NOT PRIME number.
- 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. - 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:

## Comments