Kiểm tra và tìm số nguyên tố tiếp theo (thuật toán cơ bản)

Triển khai thuật toán kiểm tra nguyên tố và tìm số nguyên tố tiếp theo không dùng thư viện – phù hợp cho số nhỏ (trong phạm vi int).

Thuật toán isPrime

• Số ≤ 1: không nguyên tố
• Số = 2: nguyên tố
• Số chẵn > 2: không nguyên tố
• Kiểm tra ước từ 3 đến √n, bước nhảy 2 (chỉ số lẻ)

Ví dụ hoàn chỉnh

import java.util.Scanner;

public class PrimeBasicDemo {
    // Kiểm tra nguyên tố tối ưu
    public static boolean isPrime(int n) {
        if (n <= 1) return false;
        if (n == 2) return true;
        if (n % 2 == 0) return false;
        for (int i = 3; i * i <= n; i += 2) {
            if (n % i == 0) return false;
        }
        return true;
    }
    
    // Tìm số nguyên tố tiếp theo
    public static int nextPrime(int n) {
        int candidate = n + 1;
        while (!isPrime(candidate)) {
            candidate++;
        }
        return candidate;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Nhập số: ");
        int num = sc.nextInt();
        
        if (isPrime(num)) {
            System.out.println(num + " là số nguyên tố");
        } else {
            System.out.println(num + " KHÔNG phải số nguyên tố");
        }
        System.out.println("Số nguyên tố tiếp theo: " + nextPrime(num));
    }
}

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ố: 13
13 là số nguyên tố
Số nguyên tố tiếp theo: 17

Độ phức tạp

• isPrime: O(√n) – đủ nhanh cho n < 10^9
• nextPrime: Tùy khoảng cách prime gap (trung bình ~ln n)

So sánh với BigInteger

Khuyến nghị: Dùng thuật toán này cho int, dùng BigInteger cho số lớn hoặc cần cryptographic certainty.