最少从数组中删除以使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