โปรแกรม Java ตรวจสอบจำนวนเฉพาะและหาจำนวนเฉพาะถัดไป (อัลกอริทึมพื้นฐาน)

จำนวนเฉพาะ (Prime Number) คือจำนวนเต็มมากกว่า 1 ที่มีตัวหารเพียง 1 และตัวมันเอง เช่น 7 = 1 × 7

อัลกอริทึมตรวจสอบ Prime

1. รับตัวแปรจำนวนเต็ม A
2. หาร A ด้วยตัวเลขจาก (A-1) ลงมาเป็น 2
3. ถ้า A หารลงตัวด้วยตัวใดตัวหนึ่ง → ไม่ใช่ prime
4. ถ้าหารไม่ลงตัวทุกตัว → เป็น prime

หมายเหตุ: เพิ่มประสิทธิภาพได้โดยตรวจสอบแค่ถึง √A

ตัวอย่างโค้ดครบถ้วน

import java.util.Scanner;

public class NextNumberIsPrime {
    public static boolean isPrime(int num) {
        if (num <= 1) return false;
        for (int i = 2; i * i <= num; i++) { // optimize: check to sqrt(num)
            if (num % i == 0) return false;
        }
        return true;
    }
    
    public static int nextPrime(int num) {
        num++;
        while (!isPrime(num)) {
            num++;
        }
        return num;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter a number: ");
        int num = sc.nextInt();
        
        if (isPrime(num)) {
            System.out.println(num + " is a prime number");
        } else {
            System.out.println(num + " is not a prime number");
        }
        
        System.out.println("Next prime number is: " + nextPrime(num));
    }
}

ผลลัพธ์

Enter a number: 25
25 is not a prime number
Next prime number is: 29

การปรับปรุงประสิทธิภาพ (Optimization)

// ตรวจสอบเฉพาะ 2 และเลขคี่
public static boolean isPrimeOptimized(int num) {
    if (num <= 1) return false;
    if (num == 2) return true;
    if (num % 2 == 0) return false;
    
    for (int i = 3; i * i <= num; i += 2) { // ข้ามเลขคู่
        if (num % i == 0) return false;
    }
    return true;
}

การเปรียบเทียบกับ BigInteger

Sieve of Eratosthenes (หา prime หลายตัวพร้อมกัน)

หาต้องการหา prime ทั้งช่วง ใช้ Sieve เร็วกว่ามาก:

public static List<Integer> sieve(int n) {
    boolean[] isPrime = new boolean[n + 1];
    Arrays.fill(isPrime, true);
    isPrime[0] = isPrime[1] = false;
    
    for (int i = 2; i * i <= n; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    List<Integer> primes = new ArrayList<>();
    for (int i = 2; i <= n; i++) if (isPrime[i]) primes.add(i);
    return primes;
}