C++ में 1 से N तक क्रमहीन सह-अभाज्य जोड़े गिनने की क्वेरी

इस समस्या में, हमें Q क्वेरी दी गई हैं जिनमें प्रत्येक में एक संख्या N है। हमारा कार्य C++ में 1 से N तक क्रमहीन सह-अभाज्य जोड़े गिनने की क्वेरी को हल करने के लिए एक प्रोग्राम बनाना है।

सह-अभाज्य को अपेक्षाकृत अभाज्य या पारस्परिक रूप से अभाज्य के रूप में भी जाना जाता है, ये संख्याओं के ऐसे जोड़े हैं जिनका केवल एक गुणनखंड होता है यानी 1।

उदाहरण से समझते हैं

इनपुट: 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)

समाधान दृष्टिकोण

समस्या का सबसे आशाजनक समाधान यूलर के टॉटिएंट फंक्शन φ(N) का उपयोग करना है। φ(N) दिए गए मान N तक सह-अभाज्य की कुल संख्या की गणना करता है। यूलर का टॉटिएंट फंक्शन है:

φ(N) = N ∏ (1 - 1/p)

जहां p, N के सभी अभाज्य गुणनखंड हैं।

अब, हम 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