在C++中查找数组中满足(A[i] % K)最大的素数K

假设我们有一个包含n个整数的数组A。我们必须找到一个元素K，使得K是素数，并且对于所有有效的i，A[i] mod K在所有可能的K值中最大。如果没有找到这样的数字，则返回-1。例如，如果A = [2, 10, 15, 7, 6, 8, 13]，则输出将为13。有三个素数2、7和13。A[i] mod 2的最大可能值为1（15 mod 2），对于7，它将为6 mod 7 = 6，而对于13，它将为10 mod 13 = 10。这是最大值。

为了最大化A[i] mod K的值，K必须是A中的最大素数，而A[i]必须是小于K的数组中最大的元素。因此，我们将只找到数组中的最大素数。为了做到这一点，我们可以使用筛法找到小于或等于数组中最大元素的所有素数。然后找到数组中的最大素数并打印出来。如果没有素数，则返回-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

更新于：2019年12月18日

80 次查看

开启您的职业生涯

完成课程获得认证

开始学习
广告