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

pythonserver side programmingprogramming更新于 2025/10/16 7:40:17

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

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

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

INF := 100001
spf := 一个包含元素 0 到 INF 的列表
定义一个函数 sieve()
对于范围从 4 到 INF 的 i，增加 2，执行
- spf[i] := 2
对于范围从 3 到 INF 的 i，执行
- 如果 i^2 > INF −
  - break
- 如果 spf[i] 与 i 相同，则
  - 对于 j，范围为 2 * i 到 INF，在每个步骤中用 i 更新，执行
    - 如果 spf[j] 与 j 相同，则
      - spf[j] := i
定义一个函数 calc_fact()。这将需要 x
ret := a new list
当 x 不等于 1 时，执行
- 在 ret 末尾插入 spf[x]
- x := x / spf[x] (仅获取整数部分)
返回 ret
从主方法执行以下操作 −
g := 0
对于 0 到 n 范围内的 i，执行
- g := gcd(a[i], g)
my_map := a new map
对于 0 到 n 范围内的 i，执行
- a[i] := a[i] / g (仅获取整数部分)
对于 0 到 n 范围内的 i，执行
- p := calc_fact(a[i])
- s := 一个新的映射
- 对于 0 到 p 大小范围内的 j，执行
  - s[p[j]] := 1
- 对于 s 中的每个 i，执行
  - my_map[i] := get(i, 0) of my_map + 1
最小值 = 10^9

对于 my_map 中的每个 i，执行

第一个 := 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))