Optimizing list comprehension to find pairs of co-prime numbers

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.

Here is my answer:

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

My answer works fine for small ranges but takes enough time if the range is increased. such as

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

is there a better way to write this or can this be optimized?

Answer 1

Since you need to calculate whether gcd == 1 for each pair of numbers, you should pre-calculate all the prime factor sets. This way, you can later very quickly determine whether two numbers are coprime by checking the intersection of their prime factor sets. We can do this fast in a sieve-like approach.

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)

After this, factors[n] will hold a set of all the prime factors of n (duh), and factored[n] all the numbers that are factored by n. This will come in handy now, since otherwise we would still need to check up to 10,000 x 10,000 pairs of numbers, which can still be rather slow in Python. But using the factors and factored sets in combination, we can now quickly find all the co-primes for a given number by eliminating the numbers that share a prime factor with 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))

For N == 100 the result looks plausible to me, and for N == 10000 it takes about 10 seconds on my computer. This might require some work to fit your actual problem, but I guess it's a good start.