problem link=[finding coprime pairs](CSES - Counting Coprime Pairs
what is optimal approach to find coprime pairs in an array…
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.
Total no of prime will be less than 10^5 so the Time complexity will be O(NlogN) where N is no. Of primes
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
Yes Man you are right , My approach is wrong.
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).