python - 优化列表理解以找到互质数对

Question

Given A,B print the number of pairs (a,b) such that GCD(a,b)=1 and 1<=a<=A and 1<=b<=B.

这是我的答案:

return len([(x,y) for x in range(1,A+1) for y in range(1,B+1) if gcd(x,y) == 1])

我的答案适用于小范围，但如果范围增加则需要足够的时间。比如

• 1 <= A <= 10^5
• 1 <= B <= 10^5

有没有更好的写法或者可以优化？

Answer 1

由于您需要为每个对 数计算gcd == 1，因此您应该预先计算所有质因数集。这样，您以后可以通过检查两个数的质因数集的交集来非常快速地确定两个数是否互质。我们可以在 sieve-like 中快速完成此操作方法。

factors = [set() for n in range(N)]
factored = collections.defaultdict(set)
for n in range(2, N):
    if not factors[n]:           # no factors yet -> n is prime
        for m in range(n, N, n): # all multiples of n up to N
            factors[m].add(n)
            factored[n].add(m)

在此之后，factors[n] 将包含一组 n(duh)和 factored[n] n 分解的所有数字。这现在会派上用场，否则我们仍然需要检查多达 10,000 x 10,000 对数字，这在 Python 中仍然相当慢。但是结合使用 factors 和 factored 集，我们现在可以通过消除与 共享质因数的数字来快速找到给定数字的所有互素>n.

for n in range(1, N):
    coprimes = set(range(1, N))  # start with all the numbers in the range
    for f in factors[n]:         # eliminate numbers that share a prime factor
        coprimes -= factored[f]
    print "%d is coprime with %r others" % (n, len(coprimes))

对于 N == 100，结果对我来说似乎是合理的，对于 N == 10000，在我的计算机上大约需要 10 秒。这可能需要一些工作来解决您的实际问题，但我想这是一个好的开始。