पायथन में जीसीडी ग्रेटर बनाने के लिए सरणी से न्यूनतम निष्कासन

मान लीजिए हमारे पास एन नंबरों की एक सूची है; हमें संख्याओं को हटाने की न्यूनतम संख्या ज्ञात करनी होगी ताकि शेष संख्याओं का GCD N संख्याओं के प्रारंभिक GCD से बड़ा हो।

इसलिए, यदि इनपुट [6,9,15,30] जैसा है, तो आउटपुट 2 होगा क्योंकि प्रारंभिक जीसीडी 3 है, इसलिए 6 और 9 को हटाने के बाद हम 15, 15> 3 के रूप में जीसीडी प्राप्त कर सकते हैं।>

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

• आईएनएफ:=100001
• spf :=0 से INF के तत्वों वाली एक सूची
• फ़ंक्शन चलनी को परिभाषित करें ()
• 4 से INF की श्रेणी में i के लिए, 2 से बढ़ाएँ, करें
  • एसपीएफ़[i] :=2
• मैं श्रेणी 3 से लेकर INF तक, करते हैं
  • अगर i^2> INF −
    • ब्रेक
  • अगर एसपीएफ [i] मैं के समान है, तो
    • जे के लिए रेंज 2 * i से INF, प्रत्येक चरण में i द्वारा अपडेट करें, करते हैं
      • यदि spf[j], j के समान है, तो
        • spf[j] :=i
• एक फंक्शन कैल्क_फैक्ट () को परिभाषित करें। इसमें x लगेगा
• रिट:=एक नई सूची
• जबकि x 1 के समान नहीं है, करें
  • सेवा के अंत में spf[x] डालें
  • x :=x / spf[x] (केवल पूर्णांक भाग प्राप्त करें)
• रिटर्न रिटर्न
• मुख्य विधि से निम्न कार्य करें -
• जी :=0
• मैं के लिए 0 से n की सीमा में, करते हैं
  • g :=gcd(a[i], g)
• my_map :=एक नया नक्शा
• मैं के लिए 0 से n की सीमा में, करते हैं
  • a[i] :=a[i] / g (केवल पूर्णांक भाग प्राप्त करें)
• मैं के लिए 0 से n की सीमा में, करते हैं
  • p :=calc_fact(a[i])
  • s :=एक नया नक्शा
  • जे के लिए 0 से लेकर पी के आकार तक, करें
    • s[p[j]] :=1
  • प्रत्येक i के लिए, करते हैं
    • my_map[i] :=my_map + 1
    . का प्राप्त करें(i, 0)
• न्यूनतम =10^9
• my_map में प्रत्येक i के लिए, करते हैं
  • पहला:=मैं
  • दूसरा:=my_map[i]
  • यदि (n - सेकंड) <=न्यूनतम, तो
    • न्यूनतम :=n - सेकंड
• यदि न्यूनतम 10^9 नहीं है, तो
  • न्यूनतम वापसी
• अन्यथा,
  • वापसी -1

उदाहरण

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

from math import gcd as __gcd
INF = 100001
spf = [i for i in range(INF)]
def sieve():
   for i in range(4, INF, 2):
      spf[i] = 2
   for i in range(3, INF):
      if i**2 > INF:
         break
      if (spf[i] == i):
         for j in range(2 * i, INF, i):
            if (spf[j] == j):
               spf[j] = i
def calc_fact(x):
   ret = []
   while (x != 1):
      ret.append(spf[x])
      x = x // spf[x]
   return ret
def minRemove(a, n):
   g = 0
   for i in range(n):
      g = __gcd(a[i], g)
   my_map = dict()
   for i in range(n):
      a[i] = a[i] // g
   for i in range(n):
      p = calc_fact(a[i])
      s = dict()
      for j in range(len(p)):
         s[p[j]] = 1
      for i in s:
         my_map[i] = my_map.get(i, 0) + 1
   minimum = 10**9
   for i in my_map:
      first = i
      second = my_map[i]
      if ((n - second) <= minimum):
         minimum = n - second
   if (minimum != 10**9):
      return minimum
   else:
      return -1
a = [6, 9, 15, 30]
n = len(a)
sieve()
print(minRemove(a, n))

इनपुट

[6, 9, 15, 30], 4

आउटपुट

2