Python 中从数组中移除元素以使最大公约数变大

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

因此，如果输入类似于 [6,9,15,30]，则输出将为 2，因为初始最大公约数为 3，因此在移除 6 和 9 后，我们可以得到最大公约数为 15，15 > 3。

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

  • INF := 100001
  • spf := 一个包含元素 0 到 INF 的列表
  • 定义一个函数 sieve()
  • 对于 i 从 4 到 INF，步长为 2，执行以下操作：
    • spf[i] := 2
  • 对于 i 从 3 到 INF，执行以下操作：
    • 如果 i^2 > INF，则：
      • 中断
    • 如果 spf[i] 等于 i，则：
      • 对于 j 从 2 * i 到 INF，每次更新步长为 i，执行以下操作：
        • 如果 spf[j] 等于 j，则：
          • spf[j] := i
  • 定义一个函数 calc_fact()。它将接收 x 作为参数
  • ret := 一个新的列表
  • 当 x 不等于 1 时，执行以下操作：
    • 在 ret 的末尾插入 spf[x]
    • x := x / spf[x]（仅获取整数部分）
  • 返回 ret
  • 从主方法执行以下操作：
  • g := 0
  • 对于 i 从 0 到 n，执行以下操作：
    • g := gcd(a[i], g)
  • my_map := 一个新的映射
  • 对于 i 从 0 到 n，执行以下操作：
    • a[i] := a[i] / g（仅获取整数部分）
  • 对于 i 从 0 到 n，执行以下操作：
    • p := calc_fact(a[i])
    • s := 一个新的映射
    • 对于 j 从 0 到 p 的大小，执行以下操作：
      • s[p[j]] := 1
    • 对于 s 中的每个 i，执行以下操作：
      • my_map[i] := 获取 my_map 中 i 对应的值，默认为 0，然后加 1
  • minimum = 10^9
  • 对于 my_map 中的每个 i，执行以下操作：
    • first := i
    • second := my_map[i]
    • 如果 (n - second) <= minimum，则：
      • minimum := n - second
  • 如果 minimum 不等于 10^9，则：
    • 返回 minimum
  • 否则，
    • 返回 -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

更新于: 2020-08-27

120 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告