जीसीडी () से सी ++ में प्रत्येक जोड़ी से मूल संख्याएं खोजें

अवधारणा

किसी दिए गए सरणी सरणी के संबंध में [] जिसमें किसी अन्य सरणी के तत्वों की हर संभावित जोड़ी की जीसीडी होती है, हमारा कार्य मूल संख्याओं को निर्धारित करना है जो जीसीडी सरणी की गणना करने के लिए उपयोग किए जाते हैं।

इनपुट

array[] = {6, 1, 1, 13}

आउटपुट

13 6
gcd(13, 13) = 13
gcd(13, 6) = 1
gcd(6, 13) = 1
gcd(6, 6) = 6

इनपुट

arr[] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 6, 6, 6, 8, 11, 13, 3, 3}

आउटपुट

13 11 8 6 6

विधि

• सबसे पहले, सरणी को घटते क्रम में क्रमबद्ध करें।

• सबसे बड़ा तत्व हमेशा मूल संख्याओं में से एक होगा। उस नंबर को बनाए रखें और उसे ऐरे से हटा दें।

• पिछले चरण में लिए गए तत्व के जीसीडी की गणना करें और वर्तमान तत्व सबसे बड़े से शुरू करें और दिए गए सरणी से जीसीडी मान को त्याग दें।

उदाहरण

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Shows utility function to print
// the contents of an array
void printArr(int array[], int n1){
   for (int i = 0; i < n1; i++)
      cout << array[i] << " ";
}
// Shows function to determine the required numbers
void findNumbers(int array[], int n1){
   // Used to sort array in decreasing order
   sort(array, array + n1, greater<int>());
   int freq1[array[0] + 1] = { 0 };
   // Here, count frequency of each element
   for (int i = 0; i < n1; i++)
      freq1[array[i]]++;
   // Shows size of the resultant array
   int size1 = sqrt(n1);
   int brr1[size1] = { 0 }, x1, l1 = 0;
   for (int i = 0; i < n1; i++) {
      if (freq1[array[i]] > 0) {
         // Here, store the highest element in
         // the resultant array
         brr1[l1] = array[i];
         //Used to decrement the frequency of that element
         freq1[brr1[l1]]--;
         l1++;
         for (int j = 0; j < l1; j++) {
            if (i != j) {
               // Calculate GCD
               x1 = __gcd(array[i], brr1[j]);
               // Decrement GCD value by 2
               freq1[x1] -= 2;
            }
         }
      }
   }
   printArr(brr1, size1);
}
// Driver code
int main(){
   /* int array[] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,1, 1, 1, 6, 6, 6, 8, 11, 13, 3, 3}; */
   int array[] = { 6, 1, 1, 13};
   int n1 = sizeof(array) / sizeof(array[0]);
   findNumbers(array, n1);
   return 0;
}

आउटपुट

13 6