Thuật toán tìm số nguyên tố lớn nhất trong mảng một chiều bằng C++

Bài toán: Hãy tìm “số nguyên tố lớn nhất” trong mảng một chiều các số nguyên. Nếu mảng không có số nguyên tố thì trả về giá trị 0.

Ví dụ:

• Input

1 3 4 5 6 11 21

• Output

So nguyen to lon nhat trong mang la: 11

• Input

1 4 6 9 12

• Output

Mang khong ton tai so nguyen to

Ý tưởng tìm số nguyên tố lớn nhất trong mảng

• Đầu tiên các bạn phải viết một hàm checkNT sẽ trả về giá trị true nếu đó là số nguyên tố, trả về false nếu không phải là số nguyên tố. Nếu các bạn chưa biết cách kiểm tra số nguyên tố thì có thể xem tại đây.
• Ta tiến hành khởi tạo giá trị của max thật bé, tốt nhất nên khởi tạo biến max là kiểu long với giá trị ngoài khả năng lưu trữ của kiểu int.
• Ta dùng một vòng lặp for duyệt lần lượt từng phần tử của mảng, nếu một phần tử của mảng vừa là số nguyên tố vừa lớn hơn max thì ta gán max bằng giá trị phần tử đó.

• if( checkNT( a[i] ) && a[i] > max ) { max = a[i]; }

• Sau khi ta duyệt hết các phần tử của mảng, nếu giá trị của max vẫn bằng giá trị khởi tạo. Tức là mảng không tồn tại số nguyên tố thì ta trả về 0. Nếu không thì ta trả về giá trị max.

Code tìm số nguyên tố lớn nhất trong mảng bằng c++

Các bạn có thể tham khảo chương trình sau

#include<iostream>
#include<math.h>
using namespace std;
const long MIN = -1000000000;
void NhapMang(int a[], int n) {
	for (int i = 0; i < n; i++) {
		cout << "Nhap a[" << i << "]: ";
		cin >> a[i];
	}
}
bool checkNT(int n) {
	if (n <= 1) return false;
	for (int i = 2; i <= sqrt(n); i++)
		if(n%i==0)
			return false;
	return true;
}
int Fun(int a[], int n) {
	long max = MIN;
	for (int i = 0; i < n; i++) {
		if (a[i] > max && checkNT(a[i]) )
			max = a[i];
	}
	if( max == MIN )
		return 0;
	else
		return max;
}
int main() {
	int a[100];
	int n;
	cout << "Nhap vao n: ";
	cin >> n;
	NhapMang(a, n);
	if (Fun(a, n) == 0)
		cout << "Mang khong ton tai so nguyen to";
	else
		cout << "So nguyen to lon nhat trong mang la: " << Fun(a, n);
	system("pause");
	return 0;
}

Sau khi chạy chương trình trên ta được kết quả

Nhap vao n: 7
Nhap a[0]: 1
Nhap a[1]: 3
Nhap a[2]: 4
Nhap a[3]: 5
Nhap a[4]: 6
Nhap a[5]: 11
Nhap a[6]: 21
So nguyen to lon nhat trong mang la: 11

Nhap vao n: 5
Nhap a[0]: 1
Nhap a[1]: 4
Nhap a[2]: 6
Nhap a[3]: 9
Nhap a[4]: 12
Mang khong ton tai so nguyen to

Bài viết mình đến đây là kết thúc. Cám ơn các bạn đã theo dõi !