Java BigInteger for Large Number Primality Testing

While solving a competitive programming problem, I revisited an interesting concept in Java’s BigInteger class — especially the meaning of certainty in isProbablePrime(). 🔹 Problem Statement Given a number n (which can be very large), determine whether it is prime or not prime. 📌 Note: The number may contain hundreds of digits, so primitive data types (int, long) are not sufficient. 🔹 Why normal prime checking fails ❌ Traditional logic like: using for loop and finding the primenumber for (int i = 2; i <= sqrt(n); i++) does not work because: 1. int / long overflow for large inputs 2. sqrt() cannot be calculated for huge numbers 3. Time complexity becomes impractical 🔹 Correct Approach using BigInteger Java provides a built-in method:-- isProbablePrime(int certainty)--- Here, certainty means: The level of confidence that the number is prime (The probability of error is less than 1 / 2^certainty) 🔹 Java Program (Competitive-ready) import java.io.*; import java.math.BigInteger; public class Solution { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader( new InputStreamReader(System.in)); String n = br.readLine().trim(); BigInteger number = new BigInteger(n); if (number.isProbablePrime(1)) { System.out.println("prime"); } else { System.out.println("not prime"); } } } ✔️ Handles very large numbers ✔️ Passes hidden test cases ✔️ Fast and reliable 🔹 Key Learning 💡 certainty is not the number to test It controls how confident Java should be Even certainty = 1 is sufficient for most competitive platforms 📚 Takeaway: When dealing with very large numbers, rely on BigInteger’s probabilistic algorithms instead of manual prime-checking logic. #Java #BigInteger #CompetitiveProgramming #ProblemSolving #LearningEveryDay #CodingTips

To view or add a comment, sign in

Explore content categories