在数组中找到素数K，使得（A [i]％K）在C ++中最大

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个n个整数的数组A。我们必须找到一个元素K，使得K为质数，并且对于所有可能的K值中的所有有效i，A [i] mod 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的最大元素。因此，我们将在中找到最大素数数组。为此，我们可以使用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

以上是 在数组中找到素数K，使得（A [i]％K）在C ++中最大 的全部内容， 来源链接： utcz.com/z/331548.html

回到顶部