Liệt kê các số nguyên tố nhỏ hơn hoặc bằng một số nguyên dương cho trước trong Java

Để liệt kê các số nguyên tố nhỏ hơn hoặc bằng một số nguyên dương cho trước trong Java, bạn có thể sử dụng thuật toán sàng Eratosthenes.

Thuật toán sàng Eratosthenes là một thuật toán đơn giản để tìm tất cả các số nguyên tố nhỏ hơn hoặc bằng một số nguyên dương n cho trước. Ý tưởng chính của thuật toán này là loại bỏ tất cả các số nguyên tố không phải là số nguyên tố bằng cách sàng lọc qua danh sách các số nguyên.

Dưới đây là đoạn code Java để liệt kê các số nguyên tố nhỏ hơn hoặc bằng một số nguyên dương cho trước bằng thuật toán sàng Eratosthenes:

public static void printPrimes(int n) {
    // tạo mảng các số nguyên từ 2 đến n và đánh dấu tất cả các số là số nguyên tố
    boolean[] isPrime = new boolean[n+1];
    for (int i = 2; i <= n; i++) {
        isPrime[i] = true;
    }
    
    // sàng lọc các số nguyên tố
    for (int i = 2; i*i <= n; i++) {
        if (isPrime[i]) {
            for (int j = i*i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    
    // in ra các số nguyên tố
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            System.out.print(i + " ");
        }
    }
}

Bên cạnh thuật toán sàng Eratosthenes, còn có nhiều cách khác để liệt kê các số nguyên tố trong Java như sử dụng thuật toán kiểm tra đơn giản hoặc thuật toán Miller-Rabin.

Dưới đây là một ví dụ về cách liệt kê các số nguyên tố bằng thuật toán kiểm tra đơn giản:

public static boolean isPrime(int n) {
    if (n <= 1) {
        return false;
    }
    for (int i = 2; i <= Math.sqrt(n); i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

public static void printPrimes(int n) {
    for (int i = 2; i <= n; i++) {
        if (isPrime(i)) {
            System.out.print(i + " ");
        }
    }
}

Tuy nhiên, thuật toán kiểm tra đơn giản này không hiệu quả khi n rất lớn, vì vậy, thuật toán sàng Eratosthenes là phương pháp tối ưu hơn để liệt kê các số nguyên tố.

One thought on “Liệt kê các số nguyên tố nhỏ hơn hoặc bằng một số nguyên dương cho trước trong Java

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *