# 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:

Subscribe
Notify of
Inline Feedbacks

HowToDoInJava provides tutorials and how-to guides on Java and related technologies.

It also shares the best practices, algorithms & solutions and frequently asked interview questions.