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: