如何编写一个简单的Java程序，找到两个数字之间最大的公约数？

这是一个问题：

“编写一个名为gcd的方法，它接受两个整数作为参数，并返回两个数字的最大公约数。两个整数a和b的最大公约数（GCD）是a和b两者的最大整数。任何数字和1的GCD是1，任何数字的GCD和0都是该数字。

计算两个数字的GCD的一种有效方法是使用Euclid算法，该算法表明以下内容：

GCD(A, B) = GCD(B, A % B) GCD(A, 0) = Absolute value of A" 

我真的很困惑如何解决这个问题。 我只想提供一些提示和提示，告诉我到目前为止我在程序中做错了什么。 （我必须放入扫描仪，这是我老师的要求。）不要给我一个完整的代码，因为我有点想自己解决这个问题。 也许只是给我一个暗示我如何结合你在上面看到的这个公式。 （如果你想知道为什么我输入== 0，那是因为我认为如果你有两个数字，比如0和90，他们的GCD会是0吗？）

另外，我的代码必须包含while循环……如果循环我会更喜欢…

提前致谢！ 🙂

我目前的计划：

 public static void main(String[] args) { Scanner console = new Scanner(System.in); int a = console.nextInt(); int b = console.nextInt(); gcd (a, b); } public static void gcd(int a, int b) { System.out.print("Type in two numbers and I will print outs its Greatest Common Divisor: "); int gcdNum1 = console.nextInt(); int gcdNum2 = console.nextInt(); while (gcdNum1 == 0) { gcdNum1 = 0; } while (gcdNum2 > gcdNum1) { int gcd = gcdNum1 % gcdNum2; } System.out.print(gcdNum1 + gcdNum2); } } 

Answer 1

递归方法是：

 static int gcd(int a, int b) { if(a == 0 || b == 0) return a+b; // base case return gcd(b,a%b); } 

使用while循环：

 static int gcd(int a, int b) { while(a!=0 && b!=0) // until either one of them is 0 { int c = b; b = a%b; a = c; } return a+b; // either one is 0, so return the non-zero value } 

当我返回a+b ，我实际上返回非零数字，假设其中一个为0。

Answer 2

您也可以使用三线方法：

 public static int gcd(int x, int y){ return (y == 0) ? x : gcd(y, x % y); } 

这里，如果y = 0 ，则返回x。 否则，再次调用gcd方法，使用不同的参数值。

Answer 3

 public static int GCD(int x, int y) { int r; while (y!=0) { r = x%y; x = y; y = r; } return x; } 

Answer 4

 import java.util.Scanner; public class Main { public static void main(String [] args) { Scanner input = new Scanner(System.in); System.out.println("Please enter the first integer:"); int b = input.nextInt(); System.out.println("Please enter the second integer:"); int d = input.nextInt(); System.out.println("The GCD of " + b + " and " + d + " is " + getGcd(b,d) + "."); } public static int getGcd(int b, int d) { int gcd = 1; if(b>d) { for(int i = d; i >=1; i--) { if(b%i==0 && d%i ==0) { return i; } } } else { for(int j = b; j >=1; j--) { if(b%j==0 && d% j==0) { return j; } } } return gcd; } } 

Answer 5

一种方法是下面的代码：

  int gcd = 0; while (gcdNum2 !=0 && gcdNum1 != 0 ) { if(gcdNum1 % gcdNum2 == 0){ gcd = gcdNum2; } int aux = gcdNum2; gcdNum2 = gcdNum1 % gcdNum2; gcdNum1 = aux; } 

您不需要递归来执行此操作。

并且要小心，它表示当数字为零时，则GCD是不为零的数字。

  while (gcdNum1 == 0) { gcdNum1 = 0; } 

您应该修改它以满足要求。

我不会告诉你如何完全修改你的代码，只是如何计算gcd。

Answer 6

 private static void GCD(int a, int b) { int temp; // make a greater than b if (b > a) { temp = a; a = b; b = temp; } while (b !=0) { // gcd of b and a%b temp = a%b; // always make a greater than bf a =b; b =temp; } System.out.println(a); } 

Answer 7

 import java.util.Scanner; class CalculateGCD { public static int calGCD(int a, int b) { int c=0,d=0; if(a>b){c=b;} else{c=a;} for(int i=c; i>0; i--) { if(((a%i)+(b%i))==0) { d=i; break; } } return d; } public static void main(String args[]) { Scanner sc=new Scanner(System.in); System.out.println("Enter the nos whose GCD is to be calculated:"); int a=sc.nextInt(); int b=sc.nextInt(); System.out.println(calGCD(a,b)); } } 

Answer 8

现在，我刚刚开始编程大约一个星期，所以没有什么花哨的，但我把这作为一个问题，并提出了这个，这对于刚刚进入编程理解的人来说可能更容易。 它使用欧几里德的方法，就像前面的例子一样。

 public class GCD { public static void main(String[] args){ int x = Math.max(Integer.parseInt(args[0]),Integer.parseInt(args[1])); int y = Math.min(Integer.parseInt(args[0]),Integer.parseInt(args[1])); for (int r = x % y; r != 0; r = x % y){ x = y; y = r; } System.out.println(y); } }