Can any one tell how can we find the pairs in an array such that LCM(a[i],a[j]) is equal to k where k<= 10^6 and 1<=i,j<=n where n<=10^5 also a[i] for any 1<=i<=n a[i]<=10^6 and also a[i] and a[j] are multiples of k