C++-এ কোয়েরি: সংখ্যাটির ঠিক চারটি স্বতন্ত্র ফ্যাক্টর আছে কিনা

এই সমস্যায়, আমাদের Q সংখ্যক কোয়েরি দেওয়া আছে, প্রতিটিতে একটি সংখ্যা N থাকে। আমাদের কাজ হল কোয়েরিগুলো সমাধান করার একটি প্রোগ্রাম তৈরি করা যাতে জানা যায় সংখ্যাটির ঠিক চারটি স্বতন্ত্র ফ্যাক্টর আছে কিনা।

সমস্যা বর্ণনা

প্রতিটি কোয়েরি সমাধান করতে, আমাদের সংখ্যা N-এর ফ্যাক্টরগুলো বের করে দেখতে হবে সেটিতে ঠিক চারটি স্বতন্ত্র ফ্যাক্টর আছে কিনা। যদি থাকে তবে YES প্রিন্ট করব, অন্যথায় NO।

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

ইনপুট: Q = 3, 4, 6, 15

আউটপুট: NO YES YES

ব্যাখ্যা

কোয়েরি ১: ৪-এর ফ্যাক্টর ১, ২, ৪ (৩টি)

কোয়েরি ২: ৬-এর ফ্যাক্টর ১, ২, ৩, ৬ (৪টি)

কোয়েরি ৩: ১৫-এর ফ্যাক্টর ১, ৩, ৫, ১৫ (৪টি)

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

এই সমস্যা সমাধানের একটি সহজ পদ্ধতি হল সংখ্যাটির সকল ফ্যাক্টর বের করা। এটি করা হয় 1 থেকে √N পর্যন্ত সংখ্যা চেক করে এবং কাউন্টার ২ করে বাড়াতে। তারপর চেক করা যে কাউন্টার ৪-এর সমান কিনা এবং সেটির ভিত্তিতে YES বা NO প্রিন্ট করা।

C++ প্রোগ্রাম উদাহরণ (সহজ পদ্ধতি)

#include <iostream>
#include <math.h>
using namespace std;

int solveQuery(int N){
    int factors = 0;
    for(int i = 1; i < sqrt(N); i++){
        if(N % i == 0){
            factors += 2;
        }
    }
    if(factors == 4){
        return 1;
    }
    return 0;
}

int main() {
    int Q = 3;
    int query[3] = {4, 6, 15};
    for(int i = 0; i < Q; i++){
        if(solveQuery(query[i]))
            cout<<"The number "<<query[i]<<" has exactly four distinct factors\n";
        else
            cout<<"The number "<<query[i]<<" does not have exactly four distinct factors\n";
    }
}

আউটপুট

The number 4 does not have exactly four distinct factors
The number 6 has exactly four distinct factors
The number 15 has exactly four distinct factors

একটি দক্ষ পদ্ধতি হল নম্বর থিওরির কনসেপ্ট ব্যবহার করা চার ফ্যাক্টর বিশিষ্ট সংখ্যার জন্য। তাই, যদি একটি সংখ্যার চারটি ফ্যাক্টর থাকে, তবে:

• যদি সংখ্যাটি একটি প্রাইম নম্বরের কিউব হয়। তবে তার চারটি স্বতন্ত্র ফ্যাক্টর থাকবে। উদাহরণ, N = (p³) হলে, ফ্যাক্টরগুলো হবে ১, p, (p²), N।

• যদি সংখ্যাটি দুটি স্বতন্ত্র প্রাইম নম্বরের গুণফল হয়। তবে সেটারও চারটি স্বতন্ত্র ফ্যাক্টর থাকবে। উদাহরণ, N = p1*p2 হলে, ফ্যাক্টরগুলো হবে ১, p1, p2, N।

C++ প্রোগ্রাম উদাহরণ (দক্ষ পদ্ধতি)

#include <bits/stdc++.h>
using namespace std;

int N = 1000;
bool hasFourFactors[1000];

void fourDistinctFactors() {
    bool primeNo[N + 1];
    memset(primeNo, true, sizeof(primeNo));
    for (int i = 2; i <= sqrt(N); i++) {
        if (primeNo[i] == true) {
            for (int j = i * 2; j <= N; j += i)
                primeNo[j] = false;
        }
    }
    vector<int> primes;
    for (int i = 2; i <= N; i++)
        if (primeNo[i])
            primes.push_back(i);
    
    memset(hasFourFactors, false, sizeof(hasFourFactors));
    for (int i = 0; i < primes.size(); ++i) {
        int p1 = primes[i];
        if (1 *(pow(p1, 3)) <= N)
            hasFourFactors[p1*p1*p1] = true;
        for (int j = i + 1; j < primes.size(); ++j) {
            int p2 = primes[j];
            if (1 * p1*p2 > N)
                break;
            hasFourFactors[p1*p2] = true;
        }
    }
}

int main() {
    int Q = 3;
    int query[] = {3, 6, 15};
    fourDistinctFactors();
    for(int i = 0; i < Q; i++){
        if(hasFourFactors[query[i]])
            cout<<"The number "<<query[i]<<" has exactly four distinct factors\n";
        else
            cout<<"The number "<<query[i]<<" does not have exactly four distinct factors\n";
    }
    return 0;
}

আউটপুট

The number 3 does not have exactly four distinct factors
The number 6 has exactly four distinct factors
The number 15 has exactly four distinct factors