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

Arnab Chakraborty

更新於: 2020-08-27

120 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習