Giả sử chúng ta có một mảng A với n số nguyên. Chúng ta phải tìm một phần tử K sao cho K là số nguyên tố, và A [i] mod K là cực đại với mọi i hợp lệ trong số tất cả các giá trị có thể có của K. Nếu không tìm thấy số nào như vậy, thì trả về -1. Ví dụ, nếu A =[2, 10, 15, 7, 6, 8, 13], thì kết quả sẽ là 13. Có ba số nguyên tố 2, 7 và 13. Giá trị lớn nhất có thể có của A [i] mod 2 là 1, (15 mod 2), cho 7, nó sẽ là 6 mod 7 =6, và cho 13, nó sẽ là 10 mod 13 =10. Đây là mức tối đa.
Để lớn nhất giá trị của A [i] mod K, K phải là số nguyên tố tối đa trong A và A [i] phải là phần tử lớn nhất từ mảng nhỏ hơn K. Vì vậy, chúng ta sẽ chỉ tìm số nguyên tố tối đa trong mảng. Để có được điều đó, chúng ta có thể sử dụng Sieve để tìm tất cả các số nguyên tố nhỏ hơn hoặc bằng phần tử lớn nhất từ mảng. Sau đó, tìm số nguyên tố lớn nhất từ mảng và in nó. Nếu không có số nguyên tố, thì trả về -1.
Ví dụ
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int getMaxPrime(int arr[], int n) {
int max_elem = *max_element(arr, arr + n);
vector<bool> prime_vals(max_elem + 1, true);
prime_vals[0] = false;
prime_vals[1] = false;
for (int p = 2; p * p <= max_elem; p++) {
if (prime_vals[p] == true) {
for (int i = p * 2; i <= max_elem; i += p)
prime_vals[i] = false;
}
}
int maximum = -1;
for (int i = 0; i < n; i++) {
if (prime_vals[arr[i]])
maximum = max(maximum, arr[i]);
}
return maximum;
}
int main() {
int arr[] = { 2, 10, 15, 7, 6, 8, 13 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Max prime is: " << getMaxPrime(arr, n);
} Đầu ra
Max prime is: 13