Kiểm Tra Số Nguyên Tố (prime Number) Trong Java - Góc Học IT

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.

• Chương trình Java tìm số ngày của tháng trong một năm
• Nhập và xuất cơ bản (basic input and output) trong Java
• Các cấu trúc điều khiển vòng lặp for và for-each trong Java
• Xây dựng và sử dụng hàm (function) trong PHP
• Lập trình giao tiếp cảm biến LDR với board mạch Arduino

5/5 - (1 bình chọn)