Course – LS – All

Get started with Spring and Spring Boot, through the Learn Spring course:

>> CHECK OUT THE COURSE

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:

public boolean isPrime(int number) {
    return number > 1 
      && IntStream.rangeClosed(2, (int) Math.sqrt(number))
      .noneMatch(n -> (number % n == 0));
}

3. Using BigInteger

BigInteger class is generally used for storing large sized integers, i.e., those greater than 64bits. 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:

public boolean isPrime(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>

The latest version of the commons-math3 can be found here.

We could do the check just by calling the method:

Primes.isPrime(number);

5. Conclusion

In this quick write-up, we have seen three ways of checking for the primality of the number.

The code for this can be found in the package com.baeldung.algorithms.primechecker over on Github.

Course – LS – All

Get started with Spring and Spring Boot, through the Learn Spring course:

>> CHECK OUT THE COURSE
res – REST with Spring (eBook) (everywhere)
Comments are closed on this article!