Kiểm tra số nguyên tố (prime number) trong Java

1. Như thế nào là một số nguyên tố (prime number)?

Một số nguyên dương chỉ chia hết cho 1 và chính nó được gọi là số nguyên tố. Ví dụ, 2, 3, 5, 7, 11, 13, 17, 19, 23,… là các số nguyên tố. Lưu ý: 0 và 1 không phải là số nguyên tố.

Ý tưởng kiểm tra một số nguyên dương n có phải là số nguyên tố hay không?

1. Nếu số nguyên dương n là 0 hoặc 1 thì kết luận không phải là số nguyên tố.

2. Nếu n không chia hết cho bất kỳ số nào từ 2 đến n-1 thì kết luận n là số nguyên tố. Ngược lại, kết luận n không phải là số nguyên tố.

Dễ thấy, chỉ có số 2 là số nguyên tố chẵn, tất cả các số chẵn khác không phải là số nguyên tố vì chúng chia hết cho 2. Do đó, thay vì phải duyệt từ 2 đến n-1, chúng ta có thể chỉ xem xét từ 2 đến n/2.

Ngoài ra, người ta đã chứng minh được rằng: chỉ cần kiểm tra xem n có chia hết cho bất kỳ số nào từ 2 đến căn bậc hai của n để xác định xem n có phải số nguyên tố hay không.

2. Chương trình kiểm tra số nguyên tố trong Java

Sử dụng vòng lặp for trong Java để kiểm tra n có chia hết cho bất kỳ số nào từ 2 đến n-1 hay không?

package primenumber;
import java.util.Scanner;

public class PrimeNumber {
    public static void main(String[] args) {
        int num;
        boolean is_prime = true;
        System.out.print("Enter a positive integer: ");
        try (Scanner scanner = new Scanner(System.in)) {
            num = scanner.nextInt();
        }
        // 0 and 1 are not prime numbers
        if (num == 0 || num == 1) {
            is_prime = false;
        }
        // loop to check if n is prime
        for (int i = 2; i <= num-1; i++) {
            if (num % i == 0) {
                is_prime = false;
                break;
            }
        }
        if (is_prime) {
            System.out.print(num + " is a prime number");
        } else {
            System.out.print(num + " is not a prime number");
        }
    }
}

Chúng ta có thể thay đổi điều kiện lặp trong for để chỉ chạy từ 2 đến n/2.

// loop to check if n is prime
for (int i = 2; i <= num/2; i++) {
    if (num % i == 0) {
        is_prime = false;
        break;
    }
}

Chúng ta có thể thay đổi điều kiện lặp trong for để chỉ chạy từ 2 đến căn bậc 2 của n (Math.sqrt(n)).

// loop to check if n is prime
for (int i = 2; i <= Math.sqrt(num); i++) {
    if (num % i == 0) {
        is_prime = false;
        break;
    }
}

Chúng ta chỉ nên duyệt đến căn bậc 2 của n để làm ngắn gọn số lần lặp trong for.

5/5 - (1 bình chọn)
Chia sẻ trên mạng xã hội:

Để lại một bình luận

Lưu ý:

1) Vui lòng bình luận bằng tiếng Việt có dấu.

2) Khuyến khích sử dụng tên thật và địa chỉ email chính xác.

3) Mọi bình luận trái quy định sẽ bị xóa bỏ.