java中怎样求两个数的最大公约数?

百度网友bbb4f305
高粉答主

2018-01-25 · 关注我不会让你失望
知道小有建树答主
回答量:238
采纳率:100%
帮助的人:11.5万
展开全部

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

  • 方法一:(辗转相除法) 
    设用户输入的两个整数为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));

    }
    }

推荐律师服务: 若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询

为你推荐:

下载百度知道APP,抢鲜体验
使用百度知道APP,立即抢鲜体验。你的手机镜头里或许有别人想知道的答案。
扫描二维码下载
×

类别

我们会通过消息、邮箱等方式尽快将举报结果通知您。

说明

0/200

提交
取消

辅 助

模 式