最大公约数环

我正在做一些自学成才的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);

任何指针？

来源

2013-05-07 mikedugan

这不是你的问题，但你可以用两个较小的开始，因为GCD永远不会大于较小的输入。 – cmd 2013-05-07 16:17:28

在这里的逻辑是错误的：

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

变化：

3210

或者代码将停止一次是看到N1 或 N2的除数，而不是他们的GCD，因为循环终止条件应该是你想要做的事情的否定。

来源

2013-05-07 16:13:27

少女时代！谢谢 – mikedugan 2013-05-07 16:18:50

什么做这样的：

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

来源

2013-05-07 16:19:21 sha1

当它达到循环连续条件时它会自动中断 – mikedugan 2013-05-07 16:41:50

你的意思是，在'd> 1'部分？ – sha1 2013-05-07 17:18:56

我测试了一些输入，但我在这里看不到任何问题。 – sha1 2013-05-07 17:29:44

公共静态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); 
}

这是一个没有遍历所有的数字是最好的方法。试着自己理解，这将有助于你开发逻辑，如果你不能理解回复我，我会解释逻辑。

来源

2013-05-07 16:38:47

这个循环基本上在一行中完成了这一切:) – mikedugan 2013-05-07 16:41:07

当两个数字非常大，例如197853,54689只要想象一下你将需要的循环数量，而这会在更短的时间内发生。：d – 2013-05-07 16:44:21

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

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

}

一切顺利！

来源

2013-08-04 18:16:32 Deepeshkumar

迭代

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

来源

2013-10-20 01:51:32

最大公约数环

回答

相关问题