Java Primality Test | HackerRank Solution

Java Primality Test on HackerRank is less about algorithms and more about knowing your standard library. The number can be up to 100 digits long, far beyond what long can hold, so a normal trial-division loop is out of the question. Java's BigInteger class has a built-in method, isProbablePrime, that does the hard work for you.

The interesting part is the word "probable". It is worth understanding what that means, what the certainty argument controls, and why the method is still safe to trust. Those are the questions an interviewer would ask if this came up.

Problem

A prime number is a natural number greater than 1 whose only positive divisors are 1 and itself. You are given one large integer n. Use BigInteger.isProbablePrime to decide whether it is prime, and print prime or not prime.

Input format: a single line containing n.

Output format: prime if n is prime, otherwise not prime, all in lowercase.

Constraints: n has at most 100 digits.

Input
13

Output
prime

13 has no divisors other than 1 and 13, so the answer is prime.

Approach

A 100-digit number is roughly 10^100. Trial division up to the square root would need around 10^50 steps, which is impossible. So we use a probabilistic test instead.

1. Read the input as a String, not as a number type. Trim it in case of stray spaces.
2. Build a BigInteger from that string. It can hold integers of any size.
3. Call isProbablePrime(certainty) and print the matching word.

How the method works, in short: it runs a set of randomised tests (Miller-Rabin rounds, and for larger numbers also a Lucas test). Each round either proves that the number is composite or fails to find a witness. A prime always passes. A composite can pass a round only by bad luck.

That gives the two key facts:

• If the method returns false, the number is definitely composite.
• If it returns true, the chance that the number is actually composite is at most 1 in 2^certainty. With certainty 10 that is under 0.1 percent, and in practice it is far smaller because the tests are much stronger than the bound promises.

Higher certainty means more rounds and more time. For a single 100-digit number, even certainty 100 runs instantly, so do not worry about the cost here.

Dry run: read "13", build BigInteger 13, isProbablePrime(10) returns true, print "prime".

Solution in Java

The older solution here was correct and used certainty 100. That is fine. I lowered it to 10 to show that you do not need a huge value, and added trim() so that trailing spaces in the input do not cause a NumberFormatException.

import java.math.BigInteger;
import java.util.Scanner;

public class Solution {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // Read as text: a 100-digit number does not fit in long.
        String text = sc.nextLine().trim();
        BigInteger n = new BigInteger(text);

        // certainty 10: a composite slips through with probability
        // at most 1 / 2^10. A "false" answer is always correct.
        boolean prime = n.isProbablePrime(10);
        System.out.println(prime ? "prime" : "not prime");
    }
}

Edge cases I ran: 1 and 0 give not prime (the method follows the mathematical definition), 2 gives prime, 4 gives not prime, 561 gives not prime (561 is a Carmichael number, which fools the simpler Fermat test but not this one), and " 97 " with spaces gives prime. For a large case, 2^127 - 1 (a 39-digit Mersenne prime) gives prime, while 2^127 + 1 gives not prime.

Output

prime

Complexity

Time: each Miller-Rabin round does modular exponentiation, roughly O(d^3) for d digits with schoolbook multiplication, and the number of rounds grows with certainty. For 100 digits this is a fraction of a millisecond.

Space: O(d) to store the number.

Common mistakes

• Reading with nextLong(). Anything above about 9.2 x 10^18 throws an InputMismatchException. Read a String and pass it to new BigInteger(...).
• Certainty 0 or less. The method then returns true without testing anything. I checked: new BigInteger("15").isProbablePrime(0) returns true.
• Negative input. The method looks at the absolute value, so -7 also returns true. That does not matter here, but in your own code check for n <= 1 first if negatives are possible.
• Wrong case in output. The expected words are lowercase "prime" and "not prime".

Related: Day 25: Running Time and Complexity checks primes by hand with an O(√n) loop, and Java BigDecimal covers the decimal sibling of BigInteger.

Tip: try to solve the problem yourself before reading the solution. Use the code as a reference to check your approach, and make sure you understand why it works.

More HackerRank solutions All coding problems MCQ practice