给定一个数字 M 和一个包含 N 个元素的列表 A (A1, A2, ...) 找到所有数字 k 以便: 1=

这是我的代码，唯一的问题是它在彼此之间使用循环，如果我的输入很大，这会减慢过程，我该如何修复它以便它需要更少的时间？

N, M = [int(v) for v in input().split()]
A = [int(v) for v in input().split()]
from math import gcd
cnt = 0
print(N)
for k in range(1, M+1):
    for i in range(N):
        if gcd(k, A[i]) == 1:
            cnt += 1
            if cnt == N:
                print(k)
    cnt = 0

输入示例:(第一行包含 N 和 M，第二行包含列表 A1、A2、...)

3 12
6 1 5

最佳答案

这是一个消除嵌套循环的快速版本:

N, M = [int(v) for v in input().split()]
A = [int(v) for v in input().split()]
from math import gcd
print(N)

l = 1
for v in A:
    l = l*v//gcd(l, v)

for k in range(1, M+1):
    if gcd(l, k) == 1:
        print(k)

它的工作原理是首先采用 A 中的值的 LCM，l。然后检查 k 和 l 的 GCD 是否为 1 就足够了，这意味着 A 中的任何值都没有公因数.

注意:如果你使用的 Python 版本比我新(3.9 或更高版本)，你可以从 math 导入 lcm 并替换 l = l*v//gcd(l, v) 与 l = lcm(l, v)。

或者，正如 Kelly Bundy 指出的那样，lcm 接受任意数量的参数，因此第一个循环可以替换为 l = lcm(*A) 如果您'正在使用 3.9 或更高版本。

https://stackoverflow.com/questions/75352040/