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.
Check a number is Prime: Java Coding Problem
Carvia Tech  May 24, 2019  3 min read  16 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.
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.
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:
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:
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

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.

The implementations mentioned above does not utilize multicore 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 multicore hardware.
public class PrimeUtils {
public static void main(String[] args) throws ExecutionException, InterruptedException {
ForkJoinPool forkJoinPool = new ForkJoinPool();
List<Integer> primeList = forkJoinPool.submit(() > new PrimeUtils().collectPrimes(1000000)).get();
System.out.println("primeList = " + primeList);
forkJoinPool.shutdown();
}
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, (int) Math.sqrt(n)).noneMatch(divisor > n % divisor == 0);
}
}
Java Coding Challenges:
 How will you check if a given sentence is a pangram
 Calculate factorial of a number in Java using recursion
 Write a program to reverse a string using recursion in Java
 Create anagram buckets from a given input array of words
 Find two numbers of which the product is maximum in an array
 Java program to check if two strings are anagrams
 How to check if the given number is palindrome in Java
Top articles in this category:
 Top 50 SDET Java Programming Interview Questions & Answers
 Check if the given number is Armstrong Number in Java
 How to check if the given number is palindrome in Java
 Calculate Fibonacci Series in Java
 Check whether given number is even or odd
 Java program to check if two strings are anagrams
 How to reverse a number in Java
Find more on this topic:
SDET Interviews
End to end automation testing using Selenium Web Driver, Rest Assured, JMeter, Junit, TestNG etc.
Last updated 1 month ago
Recommended books for interview preparation:
Facebook Page
Similar Posts
 Find two numbers of which the product is maximum in an array
 Write a program to reverse the order of words in a string
 Check whether given number is even or odd
 Check a number is Prime: Java Coding Problem
 Create anagram buckets from a given input array of words
 Java program to check if two strings are anagrams
 How will you compare two java objects
 Find longest nonrepeating substring from a given string in Java
 Write a program to reverse a string using recursion in Java
 Calculate factorial of a number in Java using recursion
Enter your email address to subscribe to this blog and receive notifications of new posts by email.