C++ में 1 से N तक अनियंत्रित सह-अभाज्य युग्मों की संख्या की गणना करने के लिए प्रश्न

इस समस्या में, हमें क्यू प्रश्न दिए गए हैं जिनमें से प्रत्येक में एक संख्या एन है। हमारा कार्य सी ++ में 1 से एन तक अनियंत्रित कोप्राइम जोड़े की संख्या की गणना करने के लिए प्रश्नों को हल करने के लिए एक प्रोग्राम बनाना है।

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

समस्या को समझने के लिए एक उदाहरण लेते हैं,

इनपुट :क्यू =2, प्रश्न =[5, 6]

आउटपुट :10

स्पष्टीकरण

जोड़े हैं:(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 5), (3, 4 ), (3, 5), (4, 5)

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

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

$$𝛷(𝑁) =/𝑁 (1 −),$$

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

अब, हम N तक अनियोजित सहअभाज्य युग्मों की संख्या की संख्या के मान की पूर्व-गणना करेंगे और फिर पूर्व-परिकलित सरणी से प्रत्येक क्वेरी का मान ज्ञात करेंगे।

उदाहरण

#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