CODEWITHSUNDEEP
javaalgorithm
Rick San Mateo
Rick San Mateo

Reputation: 21

Greatest Common Divisor Challenge(Euclidean Algorithm)

everyone I've tried to solve the Greatest Common Divisor and it seem running well but i think its long code and I'm new to java and i need some advice what can i improve with the code.

    public static void main(String[] args) {
        System.out.println(GCD(888,54));
    }
    public static int GCD(int a, int b){
        int r = a % b;
        if(r != 0){
        int rem = b % r;
        if (rem > 10){
                int aRem = r % rem;
                if (aRem < 10){
                    return aRem;
                }else {
                    int bRem = rem % aRem;
                    return bRem;
                }
            }else {
                return rem;
            }
        }else {
            return r;
        }
    }
}

Upvotes: 0

Views: 117

Answers (3)

xenteros
xenteros

Reputation: 15852

The iterative way of implementing GCD in Java is the following:

public static int GCD(int a, int b) {
    while (b != 0) {
        int temp = a;
        a = b;
        b = temp%b;
    }
    return a;
}

This is an alternative to the recursive solution from Peter. The advantage is, that is won't use Stack space that much. It has the same time complexity but better memory complexity (O(1)) and will work for all valid data not risking the StackOverflowError.

Upvotes: 1

Peter Gerald
Peter Gerald

Reputation: 68

You can do this using recursion as well. Try using this code in your method.

public static int GCD(int a, int b){
        if(b == 0){
            return a;
        }
        return GCD(b, a%b);
    }

Upvotes: 1

SK -
SK -

Reputation: 469

You can just do using a for loop.

Sample code.

public static int GCD(int a, int b){
  int gcd = 1;
  for(int i = 1; i <= a && i <= b; i++){
      if(a%i==0 && b%i==0)
         gcd = i;
  }
  return gcd;
}

Upvotes: 0

Related Questions