রেঞ্জে প্রাইম ফ্যাক্টরের ক্ষমতার GCD ১ হলে সংখ্যা গণনা (C++)

দুটি সংখ্যা start এবং end দেওয়া আছে যা একটি রেঞ্জ নির্দেশ করে। লক্ষ্য হল রেঞ্জ [start, end]-এ থাকা যেসব সংখ্যার প্রাইম ফ্যাক্টরাইজেশনে সব প্রাইম ফ্যাক্টরের পাওয়ারের GCD ১।

যদি কোনো সংখ্যার প্রাইম ফ্যাক্টরাইজেশন 2^p * 3^q * 5^r ... হয়, তবে p, q, r...-এর GCD হবে ১।

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

উদাহরণ ১

ইনপুট - start = 1, end = 10

আউটপুট - প্রাইম ফ্যাক্টরের পাওয়ারের GCD ১ হলে সংখ্যা: ৬

ব্যাখ্যা - সংখ্যাগুলো: 2 (2¹), 3 (3¹), 5 (5¹), 7 (7¹), 8 (2³), 10 (2¹×5¹)। সবগুলোর পাওয়ারের GCD ১।

উদাহরণ ২

ইনপুট - start = 11, end = 20

আউটপুট - প্রাইম ফ্যাক্টরের পাওয়ারের GCD ১ হলে সংখ্যা: ৯

ব্যাখ্যা - সংখ্যাগুলো: 11 (11¹), 12 (3¹×2²), 13 (13¹), 14 (2¹×7¹), 15 (3¹×5¹), 17 (17¹), 18 (2¹×3²), 19 (19¹), 20 (2²×5¹)। সবগুলোর পাওয়ারের GCD ১।

প্রোগ্রামে ব্যবহৃত পদ্ধতি

এই পদ্ধতিতে রেঞ্জে থাকা নন-পারফেক্ট পাওয়ার সংখ্যাগুলো গণনা করা হয়। নন-পারফেক্ট পাওয়ারগুলো উপরের শর্ত পূরণ করে। তাই উত্তর = (start-end+1) - (রেঞ্জে পারফেক্ট পাওয়ার সংখ্যা)।

রেঞ্জ ভেরিয়েবল start এবং end ইনপুট নিন।
ভেক্টর vec পাওয়ার > ৩ সংরক্ষণের জন্য।
সেট sett পারফেক্ট স্কয়ার সংরক্ষণের জন্য।
সেট sett_2 নন-পারফেক্ট স্কয়ার সংরক্ষণের জন্য।
calculate() ফাংশন vec, sett, sett_2 পূরণ করে।
i=2 থেকে ii*i সেটে ইনসার্ট করুন।
যদি sett.find(i) != sett.end() হয় তবে i পারফেক্ট স্কয়ার, তাই ক কিছু করবেন না।
হোয়াইল লুপ: কারেন্ট নাম্বারের পাওয়ার large-এর চেয়ে কম থাকা পর্যন্ত। অড পাওয়ার sett_2-এ ইনসার্ট করুন (ইভেন পাওয়ার পারফেক্ট স্কয়ার, তাই sett-এ আছে)।
শেষে sett_2-এর সোর্টেড ভ্যালু vec-এ ইনসার্ট করুন।
ফাংশন GCD_1(long int start, long int end) রেঞ্জ ইনপুট নিয়ে ফলাফল রিটার্ন করে।
calculate() কল করুন।
রেঞ্জে পারফেক্ট স্কয়ার: per_sq = floor(sqrtl(end)) - floor(sqrtl(start-1))।
vec-এ আপার বাউন্ড এবং লোয়ার বাউন্ড দিয়ে top এবং bottom বের করুন।
পারফেক্ট পাওয়ার: per_pow = per_sq + (top - bottom)।
উত্তর: count = (end - start + 1) - per_pow।
count রিটার্ন করুন।

উদাহরণ কোড

#include <bits/stdc++.h>
using namespace std;
#define size 1000005
#define large 1e18
vector<long int> vec;
set<long int> sett;
set<long int> sett_2;

void calculate() {
    for (long int i = 2; i < size; i++) {
        sett.insert(i * i);
        if (sett.find(i) != sett.end()) continue;
        long int total = i;
        while (i * i <= large / total) {
            total *= (i * i);
            sett_2.insert(total);
        }
    }
    for (auto it: sett_2) vec.push_back(it);
}

long int GCD_1(long int start, long int end) {
    calculate();
    long int per_sq = floor(sqrtl(end)) - floor(sqrtl(start - 1));
    long int top = upper_bound(vec.begin(), vec.end(), end) - vec.begin();
    long int bottom = lower_bound(vec.begin(), vec.end(), start) - vec.begin();
    long int per_pow = per_sq + (top - bottom);
    long int count = (end - start + 1) - per_pow;
    return count;
}

int main() {
    long int start = 10, end = 40;
    cout << "Count of numbers in a range having GCD of powers of prime factors equal to 1 are: " << GCD_1(start, end);
    return 0;
}

উপরের কোড রান করলে নিচের আউটপুটটি পাওয়া যাবে:

আউটপুট

Count of numbers in a range having GCD of powers of prime factors equal to 1 are: 7