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!