C++-এ বাইনারি রিপ্রেজেন্টেশনে প্রাইম সেট বিট যুক্ত সংখ্যা গণনা

এই সমস্যায়, দুটি পূর্ণসংখ্যা L এবং R দেওয়া আছে। L থেকে R পর্যন্ত যেসব সংখ্যার বাইনারি রিপ্রেজেন্টেশনে সেট বিট (১-এর সংখ্যা) একটি মৌলিক সংখ্যা, তাদের মোট সংখ্যা বের করতে হবে।

উদাহরণ:

ইনপুট: L = 7, R = 12 আউটপুট: 6 ব্যাখ্যা:
7 -> 111, সেট বিট = 2 (মৌলিক)
8 -> 1000, সেট বিট = ১ (মৌলিক নয়)
9 -> 1001, সেট বিট = ২ (মৌলিক)
10 -> 1010, সেট বিট = ২ (মৌলিক)
11 -> 1011, সেট বিট = ৩ (মৌলিক)
12 -> 1100, সেট বিট = ২ (মৌলিক)

সমাধান: রেঞ্জের প্রতিটি সংখ্যা ট্রাভার্স করে __builtin_popcount() ফাংশন দিয়ে সেট বিট গণনা করব। তারপর সেট বিটটি মৌলিক কিনা চেক করব। মৌলিক হলে কাউন্ট বাড়াব।

উদাহরণ

#include <iostream>
using namespace std;

bool isPrimeNumber(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n%2 == 0 || n%3 == 0) return false;
    for (int i=5; i*i<=n; i=i+6)
        if (n%i == 0 || n%(i+2) == 0)
            return false;
    return true;
}

void printPrimeSetBits(int l, int r) {
    int tot_bit, count = 0;
    for (int i = l; i <= r; i++) {
        tot_bit = __builtin_popcount(i);
        if (isPrimeNumber(tot_bit))
            count++;
    }
    cout << count;
}

int main() {
    int L = 7, R = 13;
    cout << "Total numbers with prime set bits between " << L << " and " << R << " are : ";
    printPrimeSetBits(L, R);
    return 0;
}

আউটপুট

Total numbers with prime set bits between 7 and 13 are : 6