java - 最大公约数环

Question

我正在做一些自学的 Java，但似乎无法找出这个循环中的问题：

问题是找到两个整数 n1 和 n2 的最大公约数，其中 d 是较小的值。方法是递减 d 直到 GCD 或它达到 1 ......这是我目前所处的位置：

    Scanner input = new Scanner(System.in);
    System.out.println("Please enter two integers: ");
    int n1 = input.nextInt();
    int n2 = input.nextInt();

    int d = 0;
    int temp = 0;
    //finds the lowest value
    if(n1 < n2) {
        temp = n1;
        n1 = n2;
        n2 = temp;
    }

    for(d = n1;(n1 % d !=0 && n2 % d != 0);d--)  {

    }

    System.out.println("The GCD of " + n1 + " and " + n2 + " is " + d);

任何指针？

Answer 1

这里的逻辑是错误的：

(n1 % d !=0 && n2 % d != 0)

改成：

(n1 % d !=0 || n2 % d != 0)

或者一旦看到 n1或n2 的除数，而不是它们的 GCD，代码将停止，因为循环终止条件应该是您想要做的否定。

Answer 2

迭代

public static long gcd(long a, long b){
   long factor= Math.max(a, b);
   for(long loop= factor;loop > 1;loop--){
      if(a % loop == 0 && b % loop == 0){
         return loop;
      }
   }
   return 1;
}

迭代欧几里得算法

public static int gcd(int a, int b) //valid for positive integers.
{
    while(b > 0)
    {
        int c = a % b;
        a = b;
        b = c;
    }
    return a;
}

优化迭代

static int gcd(int a,int b)
    {
        int min=a>b?b:a,max=a+b-min, div=min;
        for(int i=1;i<min;div=min/++i)
            if(max%div==0)
                return div;
        return 1;
    }

递归的

public static long gcd(long a, long b){
   if(a == 0) return b;
   if(b == 0) return a;
   if(a > b) return gcd(b, a % b);
   return gcd(a, b % a);
}

内置

import java.math.BigInteger;

public static long gcd(long a, long b){
   return BigInteger.valueOf(a).gcd(BigInteger.valueOf(b)).longValue();
}

通过 - http://rosettacode.org/wiki/Greatest_common_divisor

Answer 3

公共静态int gcd（int a，int b）

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

这是最好的方法，无需遍历所有数字。尝试自己理解，因为这将有助于您开发逻辑，如果您无法理解回复我，我将解释逻辑。

Answer 4

这个问题也可以用不同的方式解决。下面的代码不是我的，但我已经很好地理解了逻辑。你的逻辑很好，正如答案所建议的那样，现在它也变得完美无瑕。我对你的建议是尝试为这种计算编写一个函数。如果这样做，您可以以非常简单的方式完成繁琐的工作。下面的代码是编写函数有用性的一个很好的例子。

 public static int gcd(int a,int b){
     if(b==0){
       return a;
     }
      return gcd(b,a%b);        
 }
 public static void main(String args[]){
     Scanner input = new Scanner(System.in);
     System.out.println("Please enter two integers: ");
     int n1 = input.nextInt();
     int n2 = input.nextInt();
     System.out.println("The GCD of " + n1 + " and " + n2 + " is " + gcd(n1,n2));

 }

一切顺利！

Answer 5

这样做怎么样：

for(d = n1; d > 1; d--)  {
    if(n1%d == 0 && n2%d == 0)
        break;
}