java 最大公约数环
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/16423776/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Greatest Common Divisor Loop
提问by mikedugan
I'm doing some self-taught Java, but can't seem to figure out the issue in this loop:
我正在做一些自学的 Java，但似乎无法弄清楚这个循环中的问题：
The question was to find the greatest common divisor of two integers n1 and n2 where d is the lesser value. The method is to decrement d until a GCD or it reaches 1...here's where I'm at so far:
问题是找到两个整数 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);
Any pointers?
任何指针？
回答by zw324
The logic in here is wrong:
这里的逻辑是错误的：
(n1 % d !=0 && n2 % d != 0)
change to:
改成：
(n1 % d !=0 || n2 % d != 0)
Or the code will stop once is saw a divisor of n1 orn2, instead of their GCD, since the loop termination condition should be the negation of what you want to do.
或者一旦看到 n1或n2的除数，而不是它们的 GCD，代码就会停止，因为循环终止条件应该是你想要做的事情的否定。
回答by Bishal Ghimire
Iterative
迭代
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;
}
Iterative Euclid's Algorithm
迭代欧几里得算法
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;
}
Optimized Iterative
优化迭代
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;
}
Recursive
递归
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);
}
Built-in
内置
import java.math.BigInteger;
public static long gcd(long a, long b){
return BigInteger.valueOf(a).gcd(BigInteger.valueOf(b)).longValue();
}
回答by sha1
What about doing like this:
这样做怎么样：
for(d = n1; d > 1; d--) {
if(n1%d == 0 && n2%d == 0)
break;
}
回答by Pratul Baheti
public static int gcd(int a,int b)
public static 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);
}
This is the best method without looping over all the numbers. Try to understand by yourself as that will help you to develop logic, in case you are not able to understand reply me back, i will explain logic.
这是最好的方法，无需遍历所有数字。试着自己理解，因为这将有助于你发展逻辑，如果你不能理解回复我，我会解释逻辑。
回答by Deepeshkumar
The problem can be solved in a different way also. Code below is not of mine but i have understood the logic well. Your logic is good and as suggested by answers it's made flawless too,now.My advice to you is to try writting a function for such calculation. If done so u can do tidious work in a very simple way. Code below is a fine example of usefullness of writting functions.
这个问题也可以用不同的方式解决。下面的代码不是我的，但我已经很好地理解了逻辑。你的逻辑很好，正如答案所建议的那样，现在它也变得完美无缺。我给你的建议是尝试为这种计算编写一个函数。如果这样做，您可以以非常简单的方式完成繁琐的工作。下面的代码是编写函数的有用性的一个很好的例子。
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));
}
All the best!
一切顺利！
