top button
Flag Notify
    Connect to us
      Facebook Login
      Site Registration Why to Join

Facebook Login
Site Registration

Best way to find if two numbers are coprime?

+4 votes
750 views

Two numbers a and b are said to be co-prime if gcd(a,b) is 1.

Now my question is about the algorithm to find out if given two numbers are co-prime.

posted Nov 29, 2013 by anonymous

Share this question
Facebook Share Button Twitter Share Button Google+ Share Button LinkedIn Share Button Multiple Social Share Button
You need to find the best algo to get the GCD of two numbers.

1 Answer

0 votes

Consider Binary GCD Algorithm and if GCD is 1 then numbers are co-prime:
(Source http://en.wikipedia.org/wiki/Binary_GCD_algorithm)

The algorithm reduces the problem of finding the GCD by repeatedly applying these identities:

  1. gcd(0, v) = v, because everything divides zero, and v is the largest number that divides v. Similarly, gcd(u, 0) = u. gcd(0, 0) is not typically defined, but it is convenient to set gcd(0, 0) = 0.
  2. If u and v are both even, then gcd(u, v) = 2·gcd(u/2, v/2), because 2 is a common divisor.
  3. If u is even and v is odd, then gcd(u, v) = gcd(u/2, v), because 2 is not a common divisor. Similarly, if u is odd and v is even, then gcd(u, v) = gcd(u, v/2).
  4. If u and v are both odd, and u ≥ v, then gcd(u, v) = gcd((u − v)/2, v). If both are odd and u < v, then gcd(u, v) = gcd((v − u)/2, u). These are combinations of one step of the simple Euclidean algorithm, which uses subtraction at each step, and an application of step 3 above. The division by 2 results in an integer because the difference of two odd numbers is even.[3]
  5. Repeat steps 2–4 until u = v, or (one more step) until u = 0. In either case, the GCD is 2kv, where k is the number of common factors of 2 found in step 2.

The algorithm requires O(n2)[4] worst-case time, where n is the number of bits in the larger of the two numbers. Although each step reduces at least one of the operands by at least a factor of 2, the subtract and shift operations take linear time for very large integers (although they're still quite fast in practice, requiring about one operation per word of the representation).

unsigned int gcd(unsigned int u, unsigned int v)
{
    // simple cases (termination)
    if (u == v)
        return u;

    if (u == 0)
        return v;

    if (v == 0)
        return u;

    // look for factors of 2
    if (~u & 1) // u is even
    {
        if (v & 1) // v is odd
            return gcd(u >> 1, v);
        else // both u and v are even
            return gcd(u >> 1, v >> 1) << 1;
    }

    if (~v & 1) // u is odd, v is even
        return gcd(u, v >> 1);

    // reduce larger argument
    if (u > v)
        return gcd((u - v) >> 1, v);

    return gcd((v - u) >> 1, u);
}
answer Nov 29, 2013 by Luv Kumar
Similar Questions
0 votes

suppose

A(n,m) = 
1 2 3         
4 5 6                            
7 8 9

and 

B(p, q) = 
1 1
1 1

What is best method to find min of square of difference of sub-matrices of A and B e.g.

sub-matrices of A =

1 2    |     2 3   |    4 5    |   5 6
3 4    |     5 6   |    7 8    |   8 9

Difference of first sub-matrix of A with B =

(1-1)  (2-1)    = |     0 1
(3-1)  (4-1)      |     2 3

sum of square of elements = 0*0 + 1*1 + 2*2 + 3*3 = 14

similar steps for other sub-matrices of A

Please suggest looking for an alternate method or algorithm which has time complexity less than O(n*m*p*q)

+7 votes

Input:
First List: 5->6->3 // represents number 563
Second List: 8->4->2 // represents number 842
Output
Resultant list: 4->7->4->0->4->6 // represents number 474046

+7 votes

A binary tree is given and two nodes of this tree is given, we have to find out the algorithm/code for lowest common ancestor of the two given nodes. Common ancestor are the nodes which can be reached from two nodes by following the parent links. Lowest common ancestor is the common ancestor which has the highest depth.

Contact Us
+91 9880187415
sales@queryhome.net
support@queryhome.net
#280, 3rd floor, 5th Main
6th Sector, HSR Layout
Bangalore-560102
Karnataka INDIA.
QUERY HOME
...