Coprime pairs.

Revision en1, by abhikolar1512, 2017-12-24 09:45:06

Suppose we are given an Array A of size N (N<=100000) and each element of array A[i]<=100000. Now I want to find rightmost element A[j] in subarray A[1]....A[i-1] for each A[i] such that gcd(A[j],A[i]) is 1 i.e. both are relatively comprime. How can this be done efficiently?

Tags gcd, math problem, euclidean algorithm, coprime

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English abhikolar1512 2017-12-24 09:46:04 14
en1 English abhikolar1512 2017-12-24 09:45:06 289 Initial revision (published)