Optimizing list comprehension to find pairs of co-prime numbers
Posted
by
user3685422
on Stack Overflow
See other posts from Stack Overflow
or by user3685422
Published on 2014-05-28T21:43:23Z
Indexed on
2014/05/29
15:28 UTC
Read the original article
Hit count: 222
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?
© Stack Overflow or respective owner
