ধরুন আমাদের n পূর্ণসংখ্যা সহ একটি অ্যারে রয়েছে। আমাদের একটি উপাদান K খুঁজে বের করতে হবে যেমন K হল প্রাইম, এবং A[i] mod K হল K-এর সম্ভাব্য সমস্ত মানের মধ্যে সব বৈধ i-এর জন্য সর্বাধিক। যদি এমন কোনও সংখ্যা না পাওয়া যায়, তাহলে -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
