Finding Greatest Common Divisor using Euclidean Algorithm

Question

I was trying to figure out a solution by which I can find GCD of 2 numbers in most optimal way, So I need some help here to figure out whether the program I came out works for all possible cases or has any case it will break down or can I improve it more to make it an optimal solution.

Program:

public static void main(String[] args) {
     int a= 153;
        int b= 81;
        boolean flag = true;
        int gcd = 1;
        while(flag)
        {
          if(a>b && a%b ==0)
           {
                flag = false;
                gcd = b;
            }
            else if(b>a && b%a ==0)
            {
                flag=false;
                gcd = a;
            }
            else if( a>b)
            a = a-b;
            else
            b = b-a;
        }
        System.out.println(gcd);

}

Kindly help me out in figuring out the proper solution , thanks in advance.

Answer 1

Try something like this. Euclids GCD algorithm basically says this: GCD of 2 numbers (we will call them bigger and smaller) is equal to the GCD of smaller number and difference between bigger and smaller number. Repeat the procedure until two numbers are the same. The below is iterative solution.

    int a= 153 , b = 81, gcd = 1;

    while( gcd != a ) {

        if( a > b ) a -= b;
        else if( b > a) b -= a;
        else gcd = a;
    }

    System.out.println(gcd);

This is recursive solution. Hope this helps.

    public static int euclidGCD(int a, int b) {
        if (b == a) return a;
        if (b > a)  return euclidGCD(b - a, a);
        else  return euclidGCD(a - b, b);
}

Here is a modification of your program. To test a program the best thing is to write down its conditions and cases. In this exercise there are two conditions:

• 1.) Number must be integer
• 2.) Number must be positive.

Dealing with numbers usually has discrete number of cases. In this exercise there are two cases:

• 1.) Numbers are equal.
• 2.) Numbers are different.

Your code is not correct when a is equal to b (try it yourself). When the numbers are different your code works fine. Below is modification.

    int a= 55;
    int b= 55;
    boolean flag = true;
    int gcd = b;
    while(flag && b != a)
    {
        if(a>b && a%b ==0)
        {
            flag = false;
            gcd = b;
        }
        else if(b>a && b%a ==0)
        {
            flag=false;
            gcd = a;
        }
        else if( a>b)
            a = a-b;
        else
            b = b-a;
    }
    System.out.println(gcd);