最大公约数循环[重复]

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

这样做怎么样：

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

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

这里的逻辑是错误的：

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

改为：

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

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