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 ?

I find this post: https://stackoverflow.com/questions/26948793/finding-whether-there-are-two-coprime-numbers-in-an-array?fbclid=IwAR27s_3krUKgvYiZJg6MR2TnPreGrCNgkyIjnwlKVln_kIg20LZwykO2Glc

But it doesn't give what i need , so i hope anyone can help me.

Thank you!