Calculating GCD

Question

I need help to get the GCD of two inputted numbers. I don't know why it won't return the GCD. For example GCD of 55 and 125 would be 5. Any help would be greatly appreciated. It must use methods, and no algorithms.

public static void main(String[] args)throws IOException {
        // TODO code application logic here
        //Intialize BufferReader
       minator);
        int gcd=GCD(numerator,denominator);
        System.out.println("GCD: "+gcd);


    }
     public static  int GCD(int numerator,int denominator){

       int remainder = numerator % denominator;

    if (remainder == 0)

        return denominator;

    else

        return GCD(denominator, remainder);

}

}

Answer 1

public static  int GCD(int numerator,int denominator){
         if(numerator < denominator){
                 int numswap=denominator;
                 denominator=numerator;
                 numerator=numswap;
        }
         int remainder=numerator%denominator; 
         if (remainder == 0){
             return denominator;
         }
         System.out.println(numerator+" "+denominator);
         return GCD(denominator, remainder);

    }

use if(numerator < denominator) instead of if(numerator > denominator)

Answer 2

I tried your code and it failed with a stack overflow exception. You should make sure to put such information in the question.

Anyway, here's a more traditional implementation of the Euclids GCD:

public static int GCD(int numerator, int denominator)
{
    if (denominator == 0)
        return numerator;

    return GCD(denominator, numerator % denominator);
}

Answer 3

Try

public static int gcd(int m,int n){
       if(n==0)
         return m;
       else if(n>m)
         return gcd(n,m);
       else
        return gcd(n,m%n);
}

Answer 4

Greatest common divisor (GCD) can be calculated with substraction, assuming the numbers are positive integers:

 public class GCD {
    public static void main(String[] args) {

        System.out.println(gcd(84,18)); //6
        System.out.println(gcd(30,60)); // 30
        System.out.println(gcd(125,55)); // 5

    }

    //only for positive integers 
    public static int gcd(int a, int b) {

        while (a != b) {

            if(a>b) {    
                a = a - b;    
            } else {    
                b = b - a;    
            }                      
        }
        return a;                
    }
}

Answer 5

The simplest, fastest and shortest way to get gcd of two numbers a and b is this recursive function:

int gcd(int a, int b) {
    if (b == 0)
        return a;
    else
        return gcd (b, a % b);
 }