Cách Kiểm tra số nguyên tố trong Java

Chắc hẳn trong quá trình học Java của các bạn sẽ có một vài bài tập về tra số nguyên tố, fibo, … hay đại loại là như thế! Vì vậy bài viết này sẽ hướng dẫn các bạn về các bài toán với số nguyên tố và fibonaci sao cho hiệu quả nhất.

- Số nguyên tố là gì?

- Số nguyên tố có thể hiểu đơn giản là số nguyên dương chỉ chia hết cho 1 và chính nó, ngoại trừ số 1.

- Sau đây là một thuật toán kiểm tra số nguyên tố trong Java và giải thích.

- Chi tiết thuật toán: Vì số nguyên tố là số nguyên lớn hơn 1 và chỉ chia hết cho 1 và chính nó, nên để kiểm tra 1 số a có là số nguyên tố hay không:

+ Nếu a < 2 thì return false.

+ Nếu a >= 2 thì kiểm tra từ 2 đến a - 1 , nếu a chia hết cho bất kì số nào trong khoảng đó thì return false, ngược lại không thỏa mãn chia hết thì return true(là số nguyên tố.)

- Chúng ta có thể kiểm tra từ 2 -> a - 1 nhưng người ta đã chứng minh chỉ cần kiểm tra từ 2 đến căn bậc 2 của a thôi mình sẽ dùng cách đó để chạy nhanh hơn (nhanh hơn nhiều)

1. Hàm kiểm tra số nguyên tố.

Return true nếu là số nguyên tố, ngược lại return false.

static boolean ktSoNguyenTo(int a) {
if (a < 2) return false;
for (int i = 2; i < Math.sqrt(a); i++) {
if (a % i == 0)
return false;
}
return true;
}

- Test thử:

package haumenphai;
public class B4 {
public static void main(String[] args) {
int a = 5;
if (ktSoNguyenTo(a)) {
System.out.println(a + " là số nguyên tố");
} else {
System.out.println(a + " không phải là số nguyên tố");
}
}
static boolean ktSoNguyenTo(int a) {
if (a < 2) return false;
for (int i = 2; i < Math.sqrt(a); i++) {
if (a % i == 0)
return false;
}
return true;
}
}

Kết quả:

5 là số nguyên tố.

Thay 5 bằng số 12 và thử lại:
12 không phải là số nguyên tố

2. Đếm và in ra số lượng số nguyên tố từ 1 đến 100.

package haumenphai;
public class B4 {
public static void main(String[] args) {
int dem = 0;
for (int i = 1; i <=100 ; i++) {
if (ktSoNguyenTo(i)) {
System.out.print(i+" ");
dem++;
}
}
System.out.println();
System.out.println("Số lượng số nguyên tố từ 1 - 100 : " + dem);

}
static boolean ktSoNguyenTo(int a) {
if (a < 2) return false;
for (int i = 2; i < Math.sqrt(a); i++) {
if (a % i == 0)
return false;
}
return true;
}
}

Kết quả:

2 3 4 5 7 9 11 13 17 19 23 25 29 31 37 41 43 47 49 53 59 61 67 71 73 79 83 89 97
Số lượng số nguyên tố từ 1 - 100 : 29

3. In ra màn hình tất cả các số nguyên tố là số fibonaci trong đoạn [a;b]

(ví dụ với a = 100 và b = 1000000 và giới hạn số fibo < 2*10^9)

package haumenphai;
public class B4 {
public static void main(String[] args) {
int min = 100;
int max = 1000000;
getFiboArr();
for (int i = 0; i < arrFibo.length; i++) {
if (arrFibo >= min && arrFibo <= max && ktSoNguyenTo(arrFibo)) {
System.out.println(arrFibo + " ");
}
}
}
static boolean ktSoNguyenTo(int a) {
if (a < 2) return false;
for (int i = 2; i < Math.sqrt(a); i++) {
if (a % i == 0)
return false;
}
return true;
}
static int[] arrFibo = new int[46];
static void getFiboArr() {
arrFibo[0] = 1;
arrFibo[1] = 1;
for (int i = 2; i < 46; i++) {
arrFibo = arrFibo[i-1] + arrFibo[i-2];
}
}
}

Kết quả:

233
1597
28657
514229

Bài tập ví dụ 4:

Kiểm tra 1 số a có phải là số fibonaci và là số nguyên tố hay không, nếu có thì in ra “a là số fibonaci và là số nguyên tố”. Nếu không phải thì kiểm tra xem số đó là số nguyên tố hay số fibonaci và thông báo. Nếu a không là số fibonaci và cũng không là số nguyên tố thì in ra thông báo “a là 1 số bình thường!”

package haumenphai;
import java.util.Scanner;
public class B4 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("Nhập vào số bạn muốn kiểm tra: ");
int a = scanner.nextInt();
if (isFibo(a) && ktSoNguyenTo(a)) {
System.out.println(a + " là số fibonaci và là số nguyên tố");
} else {
if (isFibo(a)) {
System.out.println(a + " chỉ là số fibonaci");
} else if (ktSoNguyenTo(a)) {
System.out.println(a + " chỉ là số nguyên tố");
} else {
System.out.println(a + " là 1 số bình thường!");
}

}
}

static boolean ktSoNguyenTo(int a) {
if (a < 2) return false;
for (int i = 2; i < Math.sqrt(a); i++) {
if (a % i == 0)
return false;
}
return true;
}

static boolean isFibo(int a) {
int[] arrFibo = new int[46];
arrFibo[0] = 1;
arrFibo[1] = 1;
for (int i = 2; i < 46; i++) {
arrFibo = arrFibo[i-1] + arrFibo[i-2];
}

for (int i = 0; i < arrFibo.length; i++) {
if (a == arrFibo) {
return true;
}
}
return false;
}

}

Kết quả test:

Nhập vào số bạn muốn kiểm tra: 2
2 là số fibonaci và là số nguyên tố

Nhập vào số bạn muốn kiểm tra: 17
17 chỉ là số nguyên tố

Nhập vào số bạn muốn kiểm tra: 1
1 chỉ là số fibonaci

Nhập vào số bạn muốn kiểm tra: 10
10 là 1 số bình thường!



Như vậy với các ví dụ về kiểm tra số nguyên tố với Java, mình hy vọng sẽ giúp ích được các bạn trong quá trình học Java. Hẹn gặp lại các bạn ở các bài viết khác nhé!

Tác giả: niithanoi.edu.vn