PythonでGCDを大きくするための配列からの最小限の削除

N個の番号のリストがあるとします。残りの数のGCDがN個の最初のGCDよりも大きくなるように、必要な数の削除の最小数を見つける必要があります。

したがって、入力が[6,9,15,30]の場合、最初のgcdは3であるため、出力は2になります。したがって、6と9を削除すると、gcdは15、15>3になります。

これを解決するには、次の手順に従います-

• INF：=100001
• spf：=要素0からINFまでのリスト
• 関数sieve（）を定義します
• 範囲4からINFのiの場合、2ずつ増やします。
  • spf [i]：=2
• 範囲3からINFのiの場合は、
  • if i ^ 2> INF −
    • 休憩
  • spf [i]がiと同じ場合、
    • 範囲2*iからINFのjの場合、各ステップでiずつ更新します。
      • spf [j]がjと同じ場合、
        • spf [j]：=i
• 関数calc_fact（）を定義します。これにはxがかかります
• ret：=新しいリスト
• xは1と同じではありませんが、
  • retの最後にspf[x]を挿入します
  • x：=x / spf [x]（整数部分のみを取得）
• return ret
• メインメソッドから次の手順を実行します-
• g：=0
• 0からnの範囲のiについては、
  • g：=gcd（a [i]、g）
• my_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]：=my_map + 1のget（i、0）
• 最小=10^ 9
• my_mapの各iについて、
  • 最初：=i
  • 秒：=my_map [i]
  • if（n-second）<=minimum、then
    • 最小：=n-2番目
• 最小値が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