Find Prime Number K in an Array with Maximum A[K] in C++

Suppose we have an array A with n integers. We have to find one element K such that K is prime, and A[i] mod K is maximum for all valid i among all possible values of K. If no such numbers are found, then return -1. For example, if A = [2, 10, 15, 7, 6, 8, 13], then the output will be 13. There are three prime numbers 2, 7, and 13. The maximum possible values of A[i] mod 2 is 1, (15 mod 2), for 7, it will be 6 mod 7 = 6, and for 13, it will be 10 mod 13 = 10. This is the maximum.

To maximize the value of A[i] mod K, the K must be max prime number in A, and A[i] must be the greatest element from the array which is less than K. So we will just find max prime number in the array. To get that we can use Sieve to find all the prime numbers less than or equal to the maximum element from the array. Then find the maximum prime number from the array and print it. If there is no prime, then return -1.

Example

 Live Demo

#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);
}

Output

Max prime is: 13