C++ में बाइनरी प्रतिनिधित्व में सेट बिट्स की अभाज्य संख्या

इस समस्या में, हमें दो पूर्णांक L और R दिए गए हैं। हमारा कार्य L से R के बीच उन संख्याओं की कुल संख्या प्रिंट करना है जिनके सेट बिट्स (set bits) की संख्या एक अभाज्य संख्या है।

आइए एक उदाहरण से समझते हैं:

इनपुट: L = 7, R = 12
आउटपुट: 6
व्याख्या:
7 -> 111, सेट बिट्स = 3, अभाज्य संख्या।
8 -> 1000, सेट बिट्स = 1, अभाज्य नहीं।
9 -> 1001, सेट बिट्स = 2, अभाज्य संख्या।
10 -> 1010, सेट बिट्स = 2, अभाज्य संख्या।
11 -> 1011, सेट बिट्स = 3, अभाज्य संख्या।
12 -> 1100, सेट बिट्स = 2, अभाज्य संख्या।

इस समस्या को हल करने के लिए, हम दी गई सीमा के प्रत्येक तत्व को पार करेंगे। और प्रत्येक संख्या में सेट बिट्स की कुल संख्या जांचेंगे, इसके लिए हम C++ के पूर्वनिर्धारित फंक्शन __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 << "कुल संख्याएं जिनके सेट बिट्स अभाज्य हैं " << L << " और " << R << " के बीच: ";
    printPrimeSetBits(L, R);
    return 0;
}

आउटपुट

कुल संख्याएं जिनके सेट बिट्स अभाज्य हैं 7 और 13 के बीच: 6