Size of array<=10^5 and each element in array is 2<=Ai<=10^5. Is there any way to calculate all the coprime pairs (Ai,Aj) where 1<=i,j<=100000 in O(nlogn) ?
Any idea how to use mobious function to solve this?
Asked
Active
Viewed 4,491 times
1
-
What if all the entries are coprime. The number of coprime pairs would be O(n ^ 2) – MrGreen Jan 12 '17 at 14:37
-
Do you want to count how many elements are coprime to a particular A_i or identify all A_j that are coprime to A_i for all i,j? E.g for the set `S = {26, 31, 80, 13}`, are you looking for `M = {1, 3, 2, 2}` (i.e. the number of coprime elements), or `A = {{31}, {26, 80, 13}, {31, 13}, {31, 80}}` (i.e. the actual coprime elements)? – Joseph Wood Jan 13 '17 at 01:08
-
I am looking for the count. 1+3+2+2=8 – rishi_07 Jan 13 '17 at 09:01
-
Possible duplicate of [Counting coprimes in a sequence](http://stackoverflow.com/questions/24807128/counting-coprimes-in-a-sequence) – Joseph Wood Jan 13 '17 at 14:43