JAVA 求最小公因数

这篇具有很好参考价值的文章主要介绍了JAVA 求最小公因数。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

JAVA 求最小公因数


题目:任意输入两个整数,如何求他们的最大公约数?

最大公约数:也称最大公因数,最大公因子,是指两个或多个整数共有约数中最大的一个。

方法一:枚举法的第一种

先输入两个整数,然后比较两个数的大小,大的整数对小的整数求余,若不为0,则让小的整数-1,再继续前面的求余操作,直至最后跳出循环,输出最大公约数。

package CSDN.资料一;

import java.util.Scanner;

/*题目:任意输入两个整数,如何求他们的最大公约数?
*最大公约数:也称最大公因数,最大公因子,是指两个或多个整数共有约数中最大的一个。
* 方法一:枚举法
* 先输入两个整数,然后比较两个数的大小,大的整数对小的整数求余,若不为0,则让小的整数-1,再继续前面的求余操作,直至最后跳出循环,输出最大公约数。
 */
public class GreatestCommonDivisor01 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入第一个整数:");
        int n = scanner.nextInt();
        System.out.println("请输入第二个整数:");
        int m = scanner.nextInt();

        //x保存小的那个数
        int x;
        if(m>n){
            x=n;
        }else{
            x=m;
        }

        //大的整数对小的整数求余,若不为0,则让小的整数-1
        while(m%x!=0||n%x!=0){
            x--;
        }
        System.out.println(x);

    }
}

运行结果:
JAVA 求最小公因数,尚硅谷,java,开发语言

方法一:枚举法的第二种

package CSDN.资料二;

import java.util.Scanner;

/*
*枚举法
*/
public class GreatestCommonDivisor03 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        System.out.println("请输入一个自然数");
        int a = in.nextInt();
        System.out.println("请再输入一个自然数");
        int b = in.nextInt();

        int gcd = 1;
        for (int i = 2; i <=a&&i<=b ; i++) {
            if(a%i==0&&b%i==0){
               gcd = i;
            }
        }

        System.out.println(a+"和"+b+"的最大公约数是"+gcd);


    }
}

方法二:展转相除法(欧几里德算法)

辗转相除法: gcd(a,b) = gcd(b,a mod b) (不妨设a>b 且r=a mod b ,r不为0)
JAVA 求最小公因数,尚硅谷,java,开发语言
如果要用辗转相除法求几个数的最大公约数,能够先求出其中任意两个数的最大公约数,再求这个最大公约数与第三个数的最大公约数,依次求下去,直到最后一个数为止。最后所得的那个最大公约数,就是全部这些数的最大公约数。

package CSDN.资料二;

import java.util.Scanner;

/*
* 展转相除法(欧几里德算法)
*/
public class GreatestCommonDivisor04 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        System.out.println("请输入一个自然数");
        int a = in.nextInt();
        System.out.println("请再输入一个自然数");
        int b =in.nextInt();
        int oa = a;
        int ob = b;
        while(b!=0){
            int r = a%b;
            a=b;
            b=r;
        }
        System.out.println(oa+"和"+ob+"的最大公约数是"+a);

    }
}

将上述的方法二封装成方法

package CSDN.资料三.封装成方法;

import java.util.Scanner;

public class GreatestCommonDivisor05 {
    public static void main(String[] args) {
        int a = 0,b=0;
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            a =sc.nextInt();
            b=sc.nextInt();
            System.out.println("欧几里得:"+gcdWhile(a,b));
        }
    }

    public static int gcdWhile(int a,int b){
        while(b>0){
            int temp = a%b;
            a=b;
            b=temp;
        }
        return a;
    }


}


方法三:递归

package CSDN._03资料三.封装成方法.递归;

import java.util.Scanner;

public class GreatestCommonDivisor06 {
    public static void main(String[] args) {
        int a = 0,b=0;
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            a =sc.nextInt();
            b=sc.nextInt();

            System.out.println("递归1:"+gcdRecursion1(a,b));
            System.out.println("递归2:"+gcdRecursion2(a,b));
        }
    }

  public static int gcdRecursion1(int a,int b){
        return b==0?a:gcdRecursion1(b,a%b);
  }

  public static int gcdRecursion2(int a,int b){
        if(a%b==0){
            return b;
        }else{
            return gcdRecursion2(b,a%b);
        }
  }


}


拓展 求最小公倍数公式为

LCM(a ,b) = (a * b) / gcd(a,b)

即 最小公倍数 = 两数之积 / 两数的最大公约数文章来源地址https://www.toymoban.com/news/detail-691231.html

综合 辗转相除法+递归 求n个数的最大公约数和最小公倍数

package CSDN._04资料四;

import java.util.Scanner;

public class GETGCDByHHH {
// 最大公约数
    static int getGCD(int a, int b) {
        if (b == 0)
            return a;
        return getGCD(b, a % b);

    }

// 最小公倍数

    static int getLCM(int a, int b) {
        return a * b / getGCD(a, b);
    }

    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        System.out.println("要输入几个数字 : ");
        int n = sc.nextInt();

        int[] data = new int[n];

        for (int i = 0; i < n; i++) {
            System.out.println("请输入第"+(i+1)+"数");
            data[i] = sc.nextInt();
        }

        int gcd = data[0];
        for(int i = 1; i < n; ++i){
            gcd = getGCD(data[0], data[i]);
        }

        int lcm = 1;
        for (int i = 1; i < n; i++) {
            lcm = getLCM(data[0],data[i]);
        }

        System.out.println("最大公约数是:" + gcd);
        System.out.println("最小公倍数是:" + lcm);

    }

}

到了这里,关于JAVA 求最小公因数的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包