Prime number checker in Java

Upasana | November 20, 2022 | 3 min read | 629 views | Java Coding Challenges


Prime numbers have great importance in computer science world. They are used in Cryptography & Security (RSA for example), Generating hashcodes, random number generators, etc. In this article we will learn if a given number is prime or not. The solution presented here may not be best optimized, but it should be sufficient from interview point of view.

RSA Algorithm & Prime Numbers

RSA encryption algorithm which is commonly used in secure commerce web sites, is based on the fact that it is easy to take two big prime numbers and multiply them, while it is computationaly difficult to do the opposite (factorize a big number into two prime numbers) on the current hardware.

Definition of Prime

A prime number is a whole number greater than 1 whose only factors are 1 and itself. The only even prime number is 2.

The first few prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23 and 29.

Trivial implementation

In very first naive attempt, we can check every integer from 2 to itself (exclusive) and test whether it divides evenly or not.

Prime number: naive approach
boolean isPrime(long n) {
    for (int i = 2; i < n; i++) {
        if (n % i == 0)
            return false;
    }
    return true;
}

Better implementation (check till square root)

There is lot of scope for the optimization in the previous code sample. Instead of checking till n (exclusive), we can check till square root of n.

\$i <= sqrt(n)\$

This is because if we list out all the factors of a number, the square root will always be in the middle.

Second optimization that we can do is to check only odd numbers, since every even number is divisible by 2 itself. We can check once if number is divisible by 2, if so it is not a prime number.

So here is the improved version:

Improved version - Prime number
boolean isPrimeV2(long n) {
    if (n % 2 == 0) return false; (1)

    for (int i = 3; i * i <= n; i += 2) { (2)
        if (n % i == 0)
            return false;
    }
    return true;
}
1 check if n is a multiple of 2
2 just check the odds till sqrt of n

Similar implementation using Java 8 version may look like below:

Java 8 equivalent
boolean isPrime(long n) {
    if (n % 2 == 0) return false;
    return n > 1 && IntStream.rangeClosed(2, (int) Math.sqrt(n))
    .noneMatch(divisor -> n % divisor == 0);
}

That’s all for this article.

Other considerations

  1. There are many efficient algorithms for finding a prime number which are out of scope for this article, as we want to focus more on the coding skills rather than pure mathematics.

  2. The implementations mentioned above does not utilize multi-core hardware, we can use parallel processing to speedup the program.

Using Java 8 Parallel Streams for performance improvement

Using parallel streams can significantly improve the performance of Prime number implementation on multi-core hardware by utilizing all the cores efficiently.

In the following program, we will collect all prime numbers upto 1000_000.

Using Java 8 parallel streams for improved performance
public class PrimeUtils {
    public static void main(String[] args) throws ExecutionException, InterruptedException {
        ForkJoinPool forkJoinPool = new ForkJoinPool(); (1)
        List<Integer> primeList = forkJoinPool.submit(() -> new PrimeUtils().collectPrimes(1000_000)).get(); (2)
        System.out.println("Prime Numbers = " + primeList);
        forkJoinPool.shutdown();    (3)
    }

    List<Integer> collectPrimes(int max) {
        return IntStream.range(2, max).parallel().filter(this::isPrime).boxed().collect(Collectors.toList());
    }

    boolean isPrime(long n) {
        if (n % 2 == 0) return false;
        return n > 1 && IntStream.rangeClosed(2, (long) Math.sqrt(n)).noneMatch(divisor -> n % divisor == 0);
    }
}
1 We are creating a new ForkJoinPool with default number of threads (which is number of cpu)
2 By submitting a parallel() stream task inside a ForkJoinPool causes all threads of that pool available for the parallel tasks
3 We shall always shutdown the ForkJoinPool once we are done with it, else resources will be blocked un-necessarily due thread leakage

Here the parallel() method on IntStream defined in collectPrime(int max) method is run inside the custom ForkJoinPool that we created in main method, due to the below trick mentioned in ForkJoinTask.fork() documentation:

Arranges to asynchronously execute this task in the pool the current task is running in, if applicable, or using the ForkJoinPool.commonPool() if not inForkJoinPool().


Java Coding Challenges:
  1. Reverse position of words in a string using recursion
  2. Check if the given string is palindrome
  3. Find two numbers of which the product is maximum in an array
  4. Create anagram buckets from a given input array of words
  5. Anagrams string checker in Java
  6. Reverse a string using recursion in Java
  7. Java Program to find Factorial of a number
See all articles in Java Coding Challenges
Top articles in this category:
  1. Java Coding Problems for SDET Automation Engineer
  2. Armstrong Number in Java
  3. Palindrome checker in Java
  4. 50 Java Interview Questions for SDET Automation Engineer
  5. Check whether given number is even or odd
  6. Anagrams string checker in Java
  7. Java Program to find Factorial of a number

Recommended books for interview preparation:

Find more on this topic: