Java Primality Test Solution


Problem Overview

Original Problem: Java Primality Test | Hackerrank

Difficulty: Easy

Category: Java Standard Library – BigInteger & Math

Description: Given a large positive integer, write a program that determines if the number is prime using Java’s BigInteger class.

Understanding the Problem

We need to determine whether a given number is a prime. Because the number can be too large for standard integer types (such as int or long), we use the BigInteger class in Java, which supports arbitrarily large integers.

Input:

A single line containing a large integer, with up to 100 digits.

Output:

A single line:

  • "prime" if the number is a prime.

  • "not prime" otherwise.

Initial Reasoning

Since the input can be extremely large, we can't use loops or normal arithmetic to check for primes. Java's BigInteger class offers the built-in method isProbablePrime(), which can help us to check the likelihood of it being prime. This method accepts a certainty parameter that increases the accuracy with a larger value, but also increases the time.

Pseudocode

// Main function:
Read the input as a string
Convert the string to a BigInteger 
If the input is probably a prime 
	Print “prime”
else 
	Print “not prime”

Solution Code

// Note this is one of many possible solutions
import java.io.*;
import java.math.*;

public class Solution {
    public static void main(String[] args) throws IOException {
        // Create a BufferedReader to read input from standard input
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        
        // Read the input number as a String
        String input = bufferedReader.readLine();
        bufferedReader.close();

        // Convert the input String to a BigInteger
        BigInteger bigInt = new BigInteger(input);
        
        // Check if the number is probably prime 
        if (bigInt.isProbablePrime(10)) {
            System.out.println("prime");
        } else {
            System.out.println("not prime");
        }
    }
}

Commenting on Alterations

While we have done our best to maintain similarity to the template code provided in the original problem, the following changes have been made to follow best practices:

  • Renamed variables:

    Using more descriptive names improves the clarity of the code and makes it easier for anyone reading the code to understand what each variable represents.