java中如何求两个数的最大公约数

Question

如题所述

Answer 1

求最大公约数：提示用户输入两个正整数，并求出它们的最大公约数。

方法一：（辗转相除法） 
设用户输入的两个整数为n1和n2且n1>n2，余数=n1%n2。当余数不为0时，把除数赋给n1做被除数，把余数赋给n2做除数再求得新余数，若还不为0再重复知道余数为0，此时n2就为最大公约数。 
例：gcd(20,8) 
20=2*8+4 
8=2*4 因此gcd(20,8)=4

代码实现：

import javax.swing.JOptionPane;public class GreatestCommonDivisor{    public static void main(String[] args){
String num1String = JOptionPane.showInputDialog("Please enter the first integer:");        int num1 = Integer.parseInt(num1String);
String num2String = JOptionPane.showInputDialog("Please enter the second integer:");        int num2 = Integer.parseInt(num2String);        if(num1<num2){            int temp=num1;
num1=num2;
num2=temp;
}        int remainder = num1%num2;        int n1=num1,n2=num2;        while(remainder!=0){
num1=num2;
num2=remainder;
remainder=num1%num2;
}

JOptionPane.showMessageDialog(null,String.format("The greatest common divisor for %d and %d is %d.",n1,n2,num2));

}
}12345678910111213141516171819202122232425262728


方法二：假设输入的两个整数为n1和n2，检查k(k=2,3,4…)是否为n1和n2的最大公约数，直到k大于两个数中较小的一个。

代码实现：

import javax.swing.JOptionPane;public class GreatestCommonDivisor{    public static void main(String[] args){

String num1String = JOptionPane.showInputDialog("Please enter the first integer:");        int num1 = Integer.parseInt(num1String);

String num2String = JOptionPane.showInputDialog("Please enter the second integer:");        int num2 = Integer.parseInt(num2String);        int gcd=1,k=1;        while(k<=num1 && k<=num2)
{            if(num1%k==0 && num2%k==0)
gcd=k;
k++;
}

JOptionPane.showMessageDialog(null,String.format("The greatest common divisor for %d and %d is %d.",num1,num2,gcd));
}
}12345678910111213141516171819202122

方法三：假设输入的两个整数为n1和n2，首先求n1和n2的最小值d，然后依次检验d，d-1，d-2，….，1是否是n1和n2的公约数，这样找到的第一个公约数就是最大公约数。

代码实现：

import javax.swing.JOptionPane;public class test{    public static void main(String[] args){

String num1String = JOptionPane.showInputDialog("Please enter the first integer:");        int num1 = Integer.parseInt(num1String);

String num2String = JOptionPane.showInputDialog("Please enter the second integer:");        int num2 = Integer.parseInt(num2String);        int d;        if(num1<num2)
d=num1;        else
d=num2;        while(d>=1){            if(num1%d==0 && num2%d==0)                break;
d--;
}

JOptionPane.showMessageDialog(null,String.format("The greatest common divisor for %d and %d is %d.",num1,num2,d));

}
}

Answer 2

以下代码为计算最大公约数和最小公倍数的工具类，其中，关于求解最大公约数部分，提供了两个方式：递归法和循环法。

import java.util.*;

/*求最大公约数和最小公倍数*/
public class MaxCommonDivisorAndMinCommonMultiple {

public static void main(String[] args) {
Scanner scan = new Scanner(System.in);// 接收控制台输入的信息

System.out.print("请输入第一个整数：");
int num1 = scan.nextInt(); // 取出控制台输入的信息

System.out.print("请输入第二个整数：");
int num2 = scan.nextInt(); // 取出控制台输入的信息

System.out.println(maxCommonDivisor(num1, num2));// 调用maxCommonDivisor()方法
System.out.println(minCommonMultiple(num1, num2));// 调用minCommonMultiple()方法
}

// 递归法求最大公约数
public static int maxCommonDivisor(int m, int n) {
if (m < n) {// 保证m>n,若m<n,则进行数据交换
int temp = m;
m = n;
n = temp;
}
if (m % n == 0) {// 若余数为0,返回最大公约数
return n;
} else { // 否则,进行递归,把n赋给m,把余数赋给n
return maxCommonDivisor(n, m % n);
}
}

// 循环法求最大公约数
public static int maxCommonDivisor2(int m, int n) {

if (m < n) {// 保证m>n,若m<n,则进行数据交换
int temp = m;
m = n;
n = temp;
}
while (m % n != 0) {// 在余数不能为0时,进行循环
int temp = m % n;
m = n;
n = temp;
}
return n;// 返回最大公约数
}

// 求最小公倍数
public static int minCommonMultiple(int m, int n) {
return m * n / maxCommonDivisor(m, n);
}
}本回答被提问者采纳

Answer 3

import java.util.Scanner;

public class Practice4_3_7 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("输入任意两个整数：");
int a = sc.nextInt();
int b = sc.nextInt();
int s = 1;
for(int i=1;i<=a && i<=b;i++){
if(a%i == 0 && b%i == 0){
s=i;
}
}
System.out.println(s);
sc.close();
}
}