Hi guys! I'm trying to find an algorithm or idea for solving this problem:
For array a[] has n element ( 2 <= n <= 10^5 , 1 <= a[i] <= 1e5 ) , find one co-prime number in this array ( if it doesn't have any,print -1) , simply: Find (i;j) ( 1<= i < j <= n) so that gcd(a[i],a[j]) = 1 -> print a[i] and a[j].
Of course, the obvious solution would be to use Euclid's algorithm for each pair (ai, aj), but its pesimistic complexity is n(n+1)/2 times the complexity of Euclid's algorithm.
Is there a way to do that in O(n) or O(n*log(n)) or better ?
But it doesn't give what i need , so i hope anyone can help me.
Thank you!