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

मान लीजिए कि हमारे पास एक सरणी A है, जहां किसी अन्य सरणी के तत्वों के प्रत्येक संभावित युग्म का GCD दिया गया है, हमें मूल संख्याएँ ढूंढनी होंगी जिनका उपयोग दिए गए GCD सरणी की गणना करने के लिए किया जाता है।

इसलिए, यदि इनपुट ए =[6, 1, 1, 13] जैसा है, तो आउटपुट [13, 6] होगा क्योंकि जीसीडी (13, 13) 13 है, जीसीडी (13, 6) 1 है, जीसीडी ( 6, 13) 1 है, gcd(6, 6) 6 है

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• n :=A का आकार

• सरणी A को अवरोही क्रम में क्रमबद्ध करें

• घटना:=आकार A[0] की एक सरणी और 0 से भरें

• मेरे लिए 0 से n की सीमा में, करें

  • घटना [ए [i]]:=घटना [ए [i]] + 1

• size :=n के वर्गमूल का पूर्णांक

• res :=A के आकार के समान आकार की एक सरणी और 0 से भरें

• एल :=0

• मेरे लिए 0 से n की सीमा में, करें

  • अगर घटना[ए[i]]> 0, तो

    • रेस [एल]:=ए [i]

    • घटना[res[l]] :=घटना[res[l]] - 1

    • एल :=एल + 1

    • j के लिए 0 से l की सीमा में, करें

      • अगर मैं j के समान नहीं हूं, तो

        • जी:=जीसीडी (ए [i], रेस [जे])

        • घटना [जी]:=घटना [जी] - 2

• रिटर्न रेस [इंडेक्स 0 से साइज तक]

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

from math import sqrt, gcd
def get_actual_array(A):
   n = len(A)
   A.sort(reverse = True)
   occurrence = [0 for i in range(A[0] + 1)]
   for i in range(n):
      occurrence[A[i]] += 1
   size = int(sqrt(n))
   res = [0 for i in range(len(A))]
   l = 0
   for i in range(n):
      if (occurrence[A[i]] > 0):
         res[l] = A[i]
         occurrence[res[l]] -= 1
         l += 1
         for j in range(l):
            if (i != j):
               g = gcd(A[i], res[j])
               occurrence[g] -= 2
   return res[:size]
A = [6, 1, 1, 13]
print(get_actual_array(A))

इनपुट

[6, 1, 1, 13]

आउटपुट

[13, 6]