एक सरणी में अभाज्य संख्या K ज्ञात करें जैसे कि (A[i]% K) C++ में अधिकतम हो

मान लीजिए कि हमारे पास n पूर्णांकों के साथ एक सरणी A है। हमें एक तत्व K को खोजना है जैसे कि K अभाज्य है, और A[i] mod K, K के सभी संभावित मानों में से सभी मान्य i के लिए अधिकतम है। यदि ऐसी कोई संख्या नहीं मिलती है, तो -1 लौटाएं। उदाहरण के लिए, यदि ए =[2, 10, 15, 7, 6, 8, 13], तो आउटपुट 13 होगा। तीन अभाज्य संख्याएँ 2, 7, और 13 हैं। ए [i] के अधिकतम संभव मान मॉड 2 1 है, (15 मॉड 2), 7 के लिए, यह 6 मॉड 7 =6 होगा, और 13 के लिए, यह 10 मॉड 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