Kiểm tra số nguyên tố và tìm số nguyên tố tiếp theo với BigInteger

Lớp java.math.BigInteger cung cấp 2 phương thức mạnh cho số lớn:

1. isProbablePrime(certainty) – Kiểm tra nguyên tố xác suất

• certainty: độ tin cậy (số lần test Miller-Rabin). Giá trị 10-20 đủ an toàn.
• Trả về true: chắc chắn nguyên tố (nếu certainty cao) hoặc rất có thể là nguyên tố
• Trả về false: chắc chắn HỢP SỐ

2. nextProbablePrime() – Tìm số nguyên tố tiếp theo

• Trả về BigInteger đầu tiên > giá trị hiện tại và là nguyên tố
• Hiệu quả cho số lớn (dùng sieve + Miller-Rabin)

Ví dụ tổng hợp

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

public class BigIntegerPrimeDemo {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Nhập số (có thể rất lớn): ");
        String input = sc.nextLine().trim();
        
        try {
            BigInteger n = new BigInteger(input);
            
            // Kiểm tra nguyên tố
            boolean isPrime = n.isProbablePrime(20); // certainty = 20
            System.out.println(n + (isPrime ? " LÀ số nguyên tố" : " KHÔNG phải số nguyên tố"));
            
            // Tìm số nguyên tố tiếp theo
            BigInteger nextPrime = n.nextProbablePrime();
            System.out.println("Số nguyên tố tiếp theo: " + nextPrime);
            
        } catch (NumberFormatException e) {
            System.out.println("Đầu vào không phải số nguyên hợp lệ!");
        }
    }
}

Kết quả

Nhập số: 25
25 KHÔNG phải số nguyên tố
Số nguyên tố tiếp theo: 29

Nhập số: 9999999967
9999999967 LÀ số nguyên tố
Số nguyên tố tiếp theo: 10000000019

So sánh với thuật toán tự viết

Lưu ý: isProbablePrime(1) nhanh nhưng có xác suất sai nhỏ. Dùng 10-20 cho production.