मान लीजिए हमारे पास n पूर्णांकों के साथ एक ऐरे A है। हमें एक तत्व K खोजना है जैसे कि K अभाज्य हो, और सभी वैध i के लिए सभी संभावित K मानों में 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[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