1. Introduction
First, let’s go over some basic theory.
Simply put, a number is prime if it’s only divisible by one and by the number itself. The non-prime numbers are called composite numbers. And number one is neither prime nor composite.
In this article, we’ll have a look at different ways to check the primality of a number in Java.
2. A Custom Implementation
With this approach, we can check if a number between 2 and (square root of the number) can accurately divide the number.
The following logic will return true if the number is prime:
boolean isPrime(int number) {
return number > 1
&& IntStream.rangeClosed(2, (int) Math.sqrt(number))
.noneMatch(n -> (number % n == 0));
}
3. Using BigInteger
Usually, we use the BigInteger class for storing large-sized integers, i.e., those greater than 64 bits. It provides a few useful APIs for working with int and long values.
One of those APIs is the isProbablePrime. This API returns false if the number is definitely a composite and returns true if there is some probability of it being prime. It is useful when dealing with large integers because it can be quite an intensive computation to verify these fully.
A quick side-note – the isProbablePrime API uses what’s known as “Miller – Rabin and Lucas – Lehmer” primality tests to check if the number is probably prime. In cases where the number is less than 100 bits, only the “Miller – Rabin” test is used, otherwise, both tests are used for checking the primality of a number.
“Miller-Rabin” test iterates a fixed number of times to determine the primality of number and this iteration count is determined by a simple check which involves the bit length of the number and the certainty value passed to the API:
boolean isPrimeByBigInteger(int number) {
BigInteger bigInt = BigInteger.valueOf(number);
return bigInt.isProbablePrime(100);
}
4. Using Apache Commons Math
Apache Commons Math API provides a method named org.apache.commons.math3.primes.Primes, which we will use for checking the primality of a number.
First, we need to import the Apache Commons Math library by adding the following dependency in our pom.xml:
<dependency>
<groupId>org.apache.commons</groupId>
<artifactId>commons-math3</artifactId>
<version>3.6.1</version>
</dependency>
We can check the latest version of the commons-math3 library here.
We could do the check just by calling the method:
Primes.isPrime(number);
5. Finding All Prime Numbers in an int Array
So far, we’ve learned three approaches to determining whether an int is a prime number. Next, let’s use these three approaches to solve a problem: finding all prime numbers in an int array.
Let’s say we have an int array:
int[] theArray = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 };
Our goal is to find all prime numbers in theArray. For simplicity, we would like to put found prime numbers into a Set:
Set<Integer> expected = Set.of(2, 3, 5, 7, 11, 13);
To solve the problem, we could loop through the array to check and collect prime numbers. However, the Stream API enables us to write more functional and readable code for this task. Next, let’s first use the self-implemented prime check method to find primes in the input array:
Set<Integer> result = Arrays.stream(theArray)
.filter(PrimeChecker::isPrime)
.boxed()
.collect(Collectors.toSet());
assertEquals(expected, result);
It’s worth mentioning that we use boxed() to convert IntStream to Stream<Integer> so that the found primes can be collected into a Set<Integer>.
Similarly, we can use the BigInteger approach or the Primes.isPrime() method from the Apache Commons Math library to do the job:
Set<Integer> resultByBigIntegerApproach = Arrays.stream(theArray)
.filter(PrimeChecker::isPrimeByBigInteger)
.boxed()
.collect(Collectors.toSet());
assertEquals(expected, resultByBigIntegerApproach);
Set<Integer> resultByApacheCommonsMath = Arrays.stream(theArray)
.filter(Primes::isPrime)
.boxed()
.collect(Collectors.toSet());
assertEquals(expected, resultByApacheCommonsMath);
As we can see, using Stream API, we can make method calls fluently, and the pipeline is pretty easy to follow.
6. Conclusion
In this quick write-up, we have seen three ways of checking for the primality of a number.
The code backing this article is available on GitHub. Once you're
logged in as a Baeldung Pro Member, start learning and coding on the project.
