（A [i]％K）がC++で最大になるような配列で素数Kを見つけます

n個の整数を持つ配列Aがあるとします。 Kが素数であるような1つの要素Kを見つける必要があり、A [i] mod Kは、Kのすべての可能な値の中ですべての有効なiに対して最大です。そのような数が見つからない場合は、-1を返します。たとえば、A =[2、10、15、7、6、8、13]の場合、出力は13になります。3つの素数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