# algorithms – How can we count the number of pairs of coprime integers in an array of integers? (CSES)

For reference, I am trying to solve this CSES Problem.

The problem basically states that given up to $$10^5$$ positive integers in the range $$(1, 10^6)$$, find the number of pairs of those positive integers that are coprime.

After some thought, I’ve come up with the following 3 ideas that I think may be on the right track, but are each missing something.

Brute-Force Idea: Simply iterate through all $$O(N^2)$$ pairs of integers in the array, and increment our answer every time the pair of integers has a Greatest Common Divisor of 1. Using the Euclidean Algorithm to find GCDs, we obtain a time complexity of $$O(N^2logN)$$, but this is too slow since $$N <= 10^5$$.

Idea #2 (Sieve of Erathosthenes): I thought that there had to be some significance to all the numbers being bounded by the rather low $$10^6$$ and not something like $$10^9$$ or $$10^{18}$$. Specifically, the bound allows us to create an Extended Sieve of Eratosthenes (basically just a normal sieve except we keep, for each number, the smallest prime number that is a factor of it). However, only comparing the smallest prime factors of 2 numbers is not enough to determine if they’re actually coprime (consider $$14$$ and $$21$$), and besides, this still involves testing all pairs of numbers, which is too slow.

Idea #3 (Principle of Inclusion and Exclusion): My most recent idea is that perhaps we can construct, for each prime number in the range $$(1, 10^6)$$, whichever given numbers are divisible by it. Then, the number of coprime pairs = the total number of pairs ($$frac{N(N-1)}{2}$$) – the number of pairs of prime numbers such that both numbers appear in at least 1 same set, and the last term can be calculated with the PIE’s formula. The problem with this is that the Principle involves the intersections of sets, and I have no idea how to calculate these intersections without re-iterating through all integers, not to mention that calculating the various terms in the formula of PIE requires iterating through all subsets of the integers ($$O(2^N)$$) – again, this approach seems too inefficient.

Overall, I’m pretty sure that at least one of these ideas is somehow on the right track, but I have been unable to find the missing link to the final solution. Can someone point me in the right direction? Thanks a lot!