Optimal approach for finding Coprime Pairs

help
1

problem link=[finding coprime pairs](CSES - Counting Coprime Pairs
what is optimal approach to find coprime pairs in an array…

1 Like
2

Find all the prime no.s till 10^6 using sieve of Erastosthenes ( Spelling of Erastosthenes might be wrong) , Then for each prime no. Find out all the no. That are divisible by that no. By going from I=p[j] -> 1000000 , with an increment of p[j] . So total no. Of pair will be = total no. Of pair - sum of cnt of pair for each p[I] . Cnt of pair for each p[I] will be x*(x-1)/2. , Where x is the no. Of no.s divisble by p[I]. Do remember that 1 is not a prime no.

3

Total no of prime will be less than 10^5 so the Time complexity will be O(NlogN) where N is no. Of primes

1 Like
4

It’s not that simple, some pairs of number can have more than one prime in common in their factorization and you are counting them multiple times in your approach

3 Likes
5

Yes Man you are right , My approach is wrong.

1 Like
6

This problem can be solve by using Mobius Function based on the inclusion-exclusion principle, by selecting one of three operations of (-1,0,1) for each number.
This selection will be dependent on the number of unique prime divisors of each number.
The time complexity will be O(NlogN).

2 Likes
7

The problem can be solved using Mobius function and inclusion-exclusion principle.
See the editorial for this problem and this gfg blog to get the answer. I did the same for the codechef problem.

3 Likes