java - 计算 GCD

Question

我需要帮助才能获得两个输入数字的 GCD。我不知道为什么它不会返回 GCD。例如 55 和 125 的 GCD 将是 5。任何帮助将不胜感激。它必须使用方法，而不是算法。

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

我尝试了您的代码，但由于堆栈溢出异常而失败。您应该确保将此类信息放在问题中。

无论如何，这里有一个更传统的 Euclids GCD 实现：

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

    return GCD(denominator, numerator % denominator);
}

Answer 2

尝试

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 3

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);

    }

使用if(numerator < denominator)而不是if(numerator > denominator)

Answer 4

获得两个数字 a 和 b 的 gcd 的最简单、最快和最短的方法是这个递归函数：

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

Answer 5

最大公约数 (GCD) 可以用减法计算，假设数字是正整数：

 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;                
    }
}