C++-এ কোয়েরি: 1 থেকে N পর্যন্ত অর্ডারহীন কো-প্রাইম পেয়ারের সংখ্যা

এই সমস্যায়, আমাদের Q কোয়েরি দেওয়া আছে যারা প্রতিটি একটি সংখ্যা N ধারণ করে। আমাদের কাজ হল 1 থেকে N পর্যন্ত অর্ডারহীন কো-প্রাইম পেয়ারের সংখ্যা কাউন্ট করার কোয়েরি সমাধান করার প্রোগ্রাম তৈরি করা।

কো-প্রাইম যাকে রিলেটিভলি প্রাইম বা মিউচুয়ালি প্রাইমও বলা হয়, সেগুলো হল সেই সংখ্যা জোড়া যাদের শুধু একটি কমন ফ্যাক্টর থাকে অর্থাৎ ১।

উদাহরণ দিয়ে বোঝা যাক

ইনপুট: Q = 2, queries = [5, 6]

আউটপুট: 10

ব্যাখ্যা

পেয়ারগুলো হল: (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 5), (3, 4), (3, 5), (4, 5)

সমাধান পদ্ধতি

এই সমস্যার সবচেয়ে সুনিশ্চিত সমাধান হল অয়লারের টোটিয়েন্ট ফাংশন phi(N) ব্যবহার করা। phi(N) দেওয়া মান N পর্যন্ত কো-প্রাইমের মোট সংখ্যা ক্যালকুলেট করে। অয়লারের টোটিয়েন্ট ফাংশন হল:

$$𝛷(𝑁) = 𝑁 ∏(1 - 1/𝑝)$$,

এখানে p হল N-এর সকল প্রাইম ফ্যাক্টর।

এখন, আমরা 1 থেকে N পর্যন্ত অর্ডারহীন কো-প্রাইম পেয়ারের সংখ্যা প্রি-ক্যালকুলেট করব। এবং তারপর প্রতিটি কোয়েরির মান প্রি-ক্যালকুলেটেড অ্যারে থেকে বের করব।

C++ প্রোগ্রাম উদাহরণ

#include <iostream>
using namespace std;

#define N 10001
int phi[N];
int CoPrimePairs[N];

void computePhi(){
    for (int i = 1; i < N; i++)
        phi[i] = i;
    for (int p = 2; p < N; p++) {
        if (phi[p] == p) {
            phi[p] = p - 1;
            for (int i = 2 * p; i < N; i += p) {
                phi[i] = (phi[i] / p) * (p - 1);
            }
        }
    }
}

void findCoPrimes() {
    computePhi();
    for (int i = 1; i < N; i++)
        CoPrimePairs[i] = CoPrimePairs[i - 1] + phi[i];
}

int main() {
    findCoPrimes();
    int Q = 3;
    int query[] = { 5, 7, 9};
    for (int i = 0; i < Q; i++)
        cout<<"For Query "<<(i+1)<<": Number of prime pairs is "<<CoPrimePairs[query[i]]<<endl;
    return 0;
}

আউটপুট

For Query 1: Number of prime pairs is 10
For Query 2: Number of prime pairs is 18
For Query 3: Number of prime pairs is 28