首页 > 其他分享 >求最大公约数

求最大公约数

时间:2023-07-01 12:56:39浏览次数:35  
标签:scanner int nextInt 最大公约数 public Scanner

求最大公约数

枚举法

public class Demo3_01 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int left = scanner.nextInt();
        int right = scanner.nextInt();
        int result = 1;
        for (int i = 2; i <= Math.min(left, right); i++) {
            if ((left % i == 0) && (right % i == 0)) {
                result = i;
            }
        }
        System.out.printf("%d和%d的最大公约数为:%d", left, right, result);
    }
}

辗转相除法

1.如果b等于0,计算结束,a就是最大公约数;
2.否则,计算a除以b的余数,让a等于b,而b等于那个余数;
3.回到第一步。
public class Demo3_01 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int a = scanner.nextInt();
        int b = scanner.nextInt();
        int r = 0;//余数
        int oa = a, ob = b;//保存a和b
        /**
         * 1.如果b等于0,计算结束,a就是最大公约数;
         * 2.否则,计算a除以b的余数,让a等于b,而b等于那个余数;
         * 3.回到第一步。
         */
        while (b != 0) {
            r = a % b;
            a = b;
            b = r;
        }
        //此时a就是最大公约数
        System.out.printf("%d和%d的最大公约数为:%d", oa, ob, a);
    }
}
/*
a    b   r
12  18  12
18  12  6
12  6   0
6   0
*/

辗转相除递归实现

public class Demo3_01 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int a = scanner.nextInt();
        int b = scanner.nextInt();
        int res = resGcd(a, b);
        //此时a就是最大公约数
        System.out.printf("%d和%d的最大公约数为:%d", a, b, res);
    }
    private static int resGcd(int a, int b) {
        if (b == 0) return a;
        return resGcd(b, a % b);
    }
}

标签:scanner,int,nextInt,最大公约数,public,Scanner
From: https://www.cnblogs.com/huxiaoan1/p/17519136.html

相关文章

  • 最大公约数和最小公倍数
    #求最大公约数86最大公约数是2deffun_gongyue(p,q):temp=p%q#2whiletemp!=0:p=q#6q=temp#q=2temp=p%q#0returnqprint(fun_gongyue(6,8))#求最小公倍数两数乘积/最大公约数d......
  • Python 求最大公约数
    题目要求求最大公约最简单快速的方式还是欧几里得算法原理:已知m、n两个不全为0的非负整数gcd(m,n)1:如果n=0,返回m作为结果,否则进入22:m对n取余,余数赋值给r3:将n赋值给m,r赋值给n,返回1参考实现defgcd(m,n):'''求最大公约数:paramm::paramn::ret......
  • 求两个数最大公约数
    公约数,亦称"公因数"。它是指能同时整除几个整数的数。如果一个整数同时是几个整数的约数,称这个整数为它们的"公约数";公约数中最大的称为最大公约数。例如:4的倍数有1,2,4;6的倍数有1,2,3,6,那么4和6的约数就是1,2,则最大公约数就是2.求解思路:求最大公约数可以使用欧几里得算法,也称辗转......
  • 欧几里得算法求最大公约数
    欧几里得算法又称辗转相除法,是指用于计算两个非负整数a,b的最大公约数。以除数和余数反复做除法运算,当余数为0时,取当前算式除数为最大公约数假如需要求18和30两个正整数的最大公约数:调用函数:print(gcd(18,30)),a,b值变化如下a    b30÷18=1……1218÷12=1……......
  • 莫比乌斯反演与最大公约数
    在数论中,有很多题目都与莫比乌斯反演有关,最典型的就是最大公约数。比如你可以见到如下常见问题。(1)已知,求为质数的的对数,或者等于1的的对数。(2)已知和,求为质数的的对数,或者等于1的的对数。(3)已知,求的对数。(4)已知和,求的对数。上面的问题其实都可以用莫比乌斯反演来解,时间复杂度都还可以......
  • 4.1 最大公约数
    第一部曲:两种思路一种枚举一种利用辗转相除法,枚举可以选择从小到大也可以选择从大到小。第二部曲: 第三部曲:if(m<n)swap(m,n); k=m%n; while(k!=0) { m=n; n=k; k=m%n; } cout<<n;第四部曲:#include<iostream>//从小到大枚举#include<algorithm>usingnamespacestd;int......
  • 最大公约数
    求任意两个正整数的最大公约数(GCD)。通过从1穷举求最大公约数:#include<iostream>usingnamespacestd;intmain(){ intm,n,a; cin>>m>>n; if(m<n) { inttemp=m; m=n; n=temp; } for(inti=1;i<=n;i++) { if(m%i==0&&n%i==0) { a=i; } } cout<<m&......
  • day 31 最大公约数
     1.使用辗转相除法2.输出结果 #include<iostream>usingnamespacestd;intg(inta,intb){if(a<b){swap(a,b);}intt=1;while(t){t=a%b;a=b;b=t;}returna;}intmain(){intnum;printf("请输入两个正整数:");inta,b;......
  • 最大公约数
    一、问题描述:二、设计思路: 三、程序流程图: 四、代码实现:#include<stdio.h>intmain(){intx,y;scanf("%d%d",&x,&y);intmin=x;if(y<min)min=y;for(inti=min;i>=1;i--){if(x%i==0&&y%i==0)......
  • 找出数组的最大公约数
    给你一个整数数组nums,返回数组中最大数和最小数的最大公约数。两个数的 最大公约数是能够被两个数整除的最大正整数。示例1:输入:nums=[2,5,6,9,10]输出:2解释:nums中最小的数是2nums中最大的数是102和10的最大公约数是2示例2:输入:nums=[7,5,6,8,3]输......