অ্যারেতে এমন মৌলিক সংখ্যা K খুঁজে বের করা যাতে (A[i] % K) সর্বোচ্চ হয় C++-তে

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