เมธอด Java สำหรับตรวจสอบจำนวนเฉพาะและหาจำนวนเฉพาะถัดไป

คลาส java.math.BigInteger มีเมธอดสำหรับจำนวนเฉพาะ:

1. isProbablePrime(int certainty)

ตรวจสอบว่าเป็นจำนวนเฉพาะหรือไม่ พารามิเตอร์ certainty = ความมั่นใจ (ค่ายิ่งมาก ยิ่งแม่นแต่ช้าลง) คืนค่า boolean

• true = น่าจะเป็น prime (probable prime)
• false = ไม่ใช่ prime แน่นอน (composite)

ตัวอย่าง

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

public class PrimeCheckExample {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter a number: ");
        long num = sc.nextLong();
        
        BigInteger bigInt = new BigInteger(String.valueOf(num));
        boolean isPrime = bigInt.isProbablePrime(10); // certainty = 10
        
        if (isPrime) {
            System.out.println(num + " is a prime number");
        } else {
            System.out.println(num + " is not a prime number");
        }
    }
}

ผลลัพธ์

Enter a number: 25
25 is not a prime number

Enter a number: 19
19 is a prime number

2. nextProbablePrime()

คืนค่า BigInteger ที่เป็นจำนวนเฉพาะตัวแรกที่มากกว่าค่าปัจจุบัน

ตัวอย่าง

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

public class NextPrimeExample {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter a number: ");
        long num = sc.nextLong();
        
        BigInteger bigInt = new BigInteger(String.valueOf(num));
        BigInteger nextPrime = bigInt.nextProbablePrime();
        
        System.out.println("Next prime number: " + nextPrime);
    }
}

ผลลัพธ์

Enter a number: 25
Next prime number: 29

ความเข้าใจเกี่ยวกับ Certainty

isProbablePrime(certainty) ใช้ Miller-Rabin primality test:

• certainty = 1: ผ่าน 1 รอบ (ความผิดพลาด < 50%)
• certainty = 10: ผ่าน 10 รอบ (ความผิดพลาด < 0.1%)
• certainty = 100: ปลอดภัยมากสำหรับคีย์เข้ารหัส

สำหรับการใช้งานทั่วไป certainty = 10-20 เพียงพอ

ข้อดีของ BigInteger

<รองรับจำนวนใหญ่ไม่มีขีดจำกัด (จำกัดแค่หน่วยความจำ)
• อัลกอริทึมทดสอบ prime เร็วและแม่นยำ
• เหมาะสำหรับ Cryptography (RSA key generation)

ตัวอย่างรวม: หา Prime ถัดไปหลายตัว

BigInteger current = new BigInteger("1000");
for (int i = 0; i < 5; i++) {
    current = current.nextProbablePrime();
    System.out.println(current);
}