最少从数组中删除以使GCD在Python中更大

假设我们有N个数字的列表；我们必须找到需要删除的最小数量的数字，以便剩余数字的GCD大于N个数字的初始GCD。

因此，如果输入像[6,9,15,30]，则输出将为2，因为初始gcd为3，因此在删除6和9之后，我们可以得到gcd为15、15> 3。

为了解决这个问题，我们将遵循以下步骤-

• INF：= 100001

• spf：=包含0到INF元素的列表

• 定义功能 sieve()

• 对于在INF范围4中的i，增加2，

• spf [i]：= 2

• 对于3到INF范围内的i

• 对于范围2 * i中的j到INF，在每一步中更新i，执行

• spf [j]：= i

• 如果spf [j]与j相同，则

• 打破

• 如果i ^ 2> INF-

• 如果spf [i]与i相同，则

• 定义一个函数calc_fact()。这将花费x

• ret：=一个新列表

• x不等于1，

• 在ret的末尾插入spf [x]

• x：= x / spf [x]（仅获取整数部分）

• 返回ret

• 从主要方法中执行以下操作-

• g：= 0

• 对于0到n范围内的i，执行

• g：= gcd（a [i]，g）

• my_map：=新映射

• 对于0到n范围内的i，执行

• a [i]：= a [i] / g（仅获取整数部分）

• 对于0到n范围内的i，执行

• my_map [i]：= my_map的get(i,0)+ 1

• s [p [j]]：= 1

• p：= calc_fact（a [i]）

• s：=新映射

• 对于范围0到p大小的j，执行

• 对于s中的每个i，

• 最小值= 10 ^ 9

• 对于my_map中的每个i，

• 最小：= n-秒

• 第一：=我

• 第二：= my_map [i]

• 如果（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