在数组中找到素数K，使得（A [i]％K）在C ++中最大
假设我们有一个n个整数的数组A。我们必须找到一个元素K，使得K为质数，并且对于所有可能的K值中的所有有效i，A[i]modK均为最大值。如果找不到此类数，则返回-1。例如，如果A=[2、10、15、7、6、8、13]，则输出将为13。存在三个质数2、7和13。A[i]的最大可能值。mod2是1，（15mod2），对于7，它将是6mod7=6，对于13，将是10mod13=10。这是最大值。
为了最大化A[i]modK的值，K必须是A中的最大素数，并且A[i]必须是数组中小于K的最大元素。因此，我们将在中找到最大素数数组。为此，我们可以使用Sieve从数组中查找所有小于或等于最大元素的质数。然后从数组中找到最大素数并打印。如果没有素数，则返回-1。
示例
#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);
}输出结果
Max prime is: 13