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

Question

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!

Answer 1

The solution is a combination of Ideas 2 and 3:

• By Idea 2, you can find a full prime factorization of each number (by dividing by the smallest prime, then dividing by the smallest prime of the result, etc.). W.l.o.g. we can assume that each prime number in the factorization has power $1$.
• Since each number is $\le 10^6$, it can have at most $7$ distinct prime divisors, since for the product of $8$ smallest primes: $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19 > 10^6$. Therefore, each number has at most $2^7$ distinct divisors.
• Now, for each divisor of each number, we record in how many numbers it appears. Since each divisor is $\le 10^6$, you can simply maintain a counter for all possible divisors. For each number, you process its divisors and increment their counter.
• Finally, using Idea 3 (PIE), for each number we can find how many numbers are not co-prime with it. For example, if the current number is $14$, then this amount is (# of numbers divisible by 7) + (# of numbers divisible by 2) - (# of numbers divisible by 14). Since the current number itself is included in this count, subtract $1$ from it.

Overall time is $2^7 \cdot 10^5 \approx 10^7$ and memory is $10^6$.

Answer 2

The second idea seems to guide you on the right track. You can use the fact that all multiplies of each prime cannot be co-prime. So, for 14, as an example, you can remove all multiples of 2 and seven from the list. Hence, you can remove all multiplies of 2 ($\frac{10^6}{2}$), plus all odd multiplies of 7 ($\frac{10^6}{7\times 2}$). Hence, you need to check the co-prime with $10^6 \times (1 - \frac{1}{2} - \frac{1}{14}) \sim428571$.

Although you cannot decrease the asymptotic complexity, as you are working on a specific range, any reasonable decreasing factor can boost the performance of your algorithm significantly.