如何优化求[1,M]内与列表A所有元素互质的数的嵌套循环代码

给定数字M和包含N个元素的列表A，需找出所有满足1≤k≤M且k与A中任意元素Ai的最大公约数（gcd）均为1的数k。

现有一段嵌套循环实现的代码，但处理大数据输入时运行速度极慢，需优化执行效率：

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

输入示例：

3 12
6 1 5

优化方案 #

原代码时间复杂度为O(M*N)，当M、N较大时性能瓶颈显著。通过质因数提取+筛法可将时间复杂度降至O(M log log M)，大幅提升效率，具体步骤如下：

1. 预处理列表A #

• 去重：避免重复处理相同元素
• 过滤无效值：移除1（任何数与1的gcd恒为1，无约束作用）、移除大于M的数（k≤M，此类数与k的gcd必为1，无约束作用）
• 若预处理后A为空，说明所有1~M的数都符合条件，直接输出即可

2. 提取所有约束质因数 #

遍历预处理后的A，分解每个数的所有质因数并去重，得到质因数集合primes。只要k不被该集合中任何质数整除，就满足与所有Ai互质的条件。

3. 筛法标记不符合条件的数 #

创建长度为M+1的布尔数组is_valid，初始标记所有数为符合条件（True）。遍历每个质因数p，将p的所有倍数标记为不符合条件（False）。

4. 输出结果 #

遍历1~M，输出所有标记为True的k。

优化后代码 #

def get_prime_factors(x):
    factors = set()
    # 提取2的因子
    while x % 2 == 0:
        factors.add(2)
        x = x // 2
    # 提取奇数因子
    i = 3
    while i * i <= x:
        while x % i == 0:
            factors.add(i)
            x = x // i
        i += 2
    if x > 1:
        factors.add(x)
    return factors

# 输入处理
N, M = map(int, input().split())
A = list(map(int, input().split()))

# 预处理A：去重+过滤无效元素
unique_A = list(set(A))
filtered_A = []
for num in unique_A:
    if num == 1 or num > M:
        continue
    filtered_A.append(num)

# 无约束条件时直接输出所有数
if not filtered_A:
    for k in range(1, M+1):
        print(k)
    exit()

# 收集所有质因数
primes = set()
for num in filtered_A:
    primes.update(get_prime_factors(num))

# 筛法标记不符合条件的数
is_valid = [True] * (M + 1)
is_valid[0] = False  # 0不在目标范围内
for p in primes:
    for multiple in range(p, M+1, p):
        is_valid[multiple] = False

# 输出符合条件的数
for k in range(1, M+1):
    if is_valid[k]:
        print(k)

内容的提问来源于stack exchange，提问作者Codeer