精华内容
下载资源
问答
  • 两个数的最大公约数

    2019-12-19 10:44:45
    目录 最大公约数 求法 代码 ...短除法求最大公约数,先用这几个数的公约数连续去除,一直除到所有的商互质为止,然后把所有的除数连乘起来,所得的积就是这几个数的最大公约数。 辗转相除法,也...

    目录

    最大公约数

    求法

    代码


    最近决定有时间好好复习一下算法,下面就从最简单的算法开始。

    最大公约数

    求法

    质因数分解

    • 把每个数分别分解质因数,再把各数中的全部公有质因数提取出来连乘,所得的积就是这几个数的最大公约数

    短除法

    • 短除法求最大公约数,先用这几个数的公约数连续去除,一直除到所有的商互质为止,然后把所有的除数连乘起来,所得的积就是这几个数的最大公约数。

    辗转相除法,也叫欧几里德算法

    • 计算两个非负整数p和q的最大公约数:若 q是0,则最大公约数为p。否则,将p除以 q得到余数r, p和q的最大公约数即为q和 r的最大公约数。

    更相减损法

    • 第一步:任意给定两个正整数;判断它们是否都是偶数。若是,则用2约简;若不是则执行第二步。
    • 第二步:以较大的数减较小的数,接着把所得的差与较小的数比较,并以大数减小数。继续这个操作,直到所得的减数和差相等为止。
    • 则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。

     具体可以参考百度百科

    代码

    GreatestCommonDivisor.java

    package algs4;
    
    
    import java.util.Stack;
    
    /**
     * @ClassName GreatestCommonDivisor
     * @Author zhangqx02
     * @Date 2019/12/19 9:38
     * @Description
     */
    
    public class GreatestCommonDivisor {
        public static void main(String[] args){
            int a = 12;
            int b = 44;
    //        int gcd = primeGcd(a,b);
    //        int gcd = euclideanGcd(a,b);
    //        int gcd = lossGcd(a,b);
            int gcd = shortGcd(a,b);
            System.out.println("("+a +","+b +")="+gcd);
        }
        /**
         * 质因数分解法
         * 质因数分解
         * 质因数分解(9张)
         * 质因数分解法:把每个数分别分解质因数,再把各数中的全部公有质因数提取出来连乘,所得的积就是这几个数的最大公约数。
         * @param a
         * @param b
         * @return
         */
        public static int primeGcd(int a,int b){
    //        Stack<Integer> gcdstack = new Stack();
            int result = 1;
            int maxa = Math.max(a, b);
            int minb = Math.min(a,b);
            for (int i = 2; i <= minb; i++){
                while (maxa % i == 0 && minb % i ==0){
    //                gcdstack.push(i);
                    result *= i;
                    maxa = maxa / i;
                    minb = minb / i;
                }
                while (maxa % i == 0 && minb % i !=0){
                    maxa = maxa / i;
                }
                while (maxa % i != 0 && minb % i == 0){
                    minb = minb / i;
                }
            }
    //        int gcd = 1;
    //        while (!gcdstack.empty()){
    //            gcd *= gcdstack.pop();
    //        }
            return result;
        }
    
        /**
         * 短除法:短除法求最大公约数,先用这几个数的公约数连续去除,一直除到所有的商互质为止,然后把所有的除数连乘起来,所得的积就是这几个数的最大公约数。
         * @param a
         * @param b
         * @return
         */
        public static int shortGcd(int a,int b){
            int result = 1;
            int numa = a;
            int numb = b;
            for (int i = 2; i <= numa && i <= numb; i++){
                if (numa % i == 0 && numb % i == 0){
                    numa = numa / i;
                    numb = numb / i;
                    result *= i;
                    i = 1;
                }
            }
       return result;
        }
    
        /**
         * 辗转相除法:辗转相除法是求两个自然数的最大公约数的一种方法,也叫欧几里德算法。
         * 计算两个非负整数p和q的最大公约数:若 q是0,则最大公约数为p。否则,将p除以 q得到余数r, p和q的最大公约数即为q和 r的最大公约数。
         * @param a 整数a
         * @param b 整数b
         * @return
         */
        public static int euclideanGcd(int a,int b){
            if (b == 0) return a;
            int r = a % b;
            return euclideanGcd(b,r);
        }
    
        /**
         * 更相减损法
         * 第一步:任意给定两个正整数;判断它们是否都是偶数。若是,则用2约简;若不是则执行第二步。
         * 第二步:以较大的数减较小的数,接着把所得的差与较小的数比较,并以大数减小数。继续这个操作,直到所得的减数和差相等为止。
         * 则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。
         * @param a
         * @param b
         * @return
         */
        public static int lossGcd(int a,int b){
            int maxa = Math.max(a,b );
            int minb = Math.min(a,b);
            int result = maxa - minb;
            while (result != minb){
                maxa = Math.max(result,minb);
                minb = Math.min(result,minb);
                result = maxa  - minb;
            }
            return result;
        }
    
    
    }
    

     

    展开全文
  • Python求两个数的最大公约数一、求最大公约数算法:1. 整数A对整数B进行取整, 余数用整数C来表示 举例: C = A % B2. 如果C等于0,则C就是整数A和整数B的最大公约数3. 如果C不等于0, 将B赋值给A, 将C赋值给B ,然后进行 ...

    bacbbf22c45bf17fed12a84fd2c2d5b8.png

    Python求两个数的最大公约数

    一、求最大公约数算法:

    1. 整数A对整数B进行取整, 余数用整数C来表示 举例: C = A % B

    2. 如果C等于0,则C就是整数A和整数B的最大公约数

    3. 如果C不等于0, 将B赋值给A, 将C赋值给B ,然后进行 1, 2 两步,直到余数为0, 则可以得知最大公约数

    二、根据算法,实现Python程序def fun(num1, num2): # 定义一个函数, 两个形参

    if num1 < num2: # 判读两个整数的大小,目的为了将大的数作为除数,小的作为被除数

    num1, num2 = num2, num1 # 如果if条件满足,则进行值的交换

    vari1 = num1 * num2 # 计算出两个整数的乘积,方便后面计算最小公倍数

    vari2 = num1 % num2 # 对2个整数进行取余数

    while vari2 != 0: # 判断余数是否为0, 如果不为0,则进入循环

    num1 = num2 # 重新进行赋值,进行下次计算

    num2 = vari2

    vari2 = num1 % num2 # 对重新赋值后的两个整数取余数

    # 直到 vari2 等于0,得到最到公约数就退出循环

    vari1 /= num2 # 得出最小公倍数

    print("最大公约数为:%d" % num2) # 输出

    print("最小公倍数为:%d" % vari1) # 输出

    fun(6, 9)

    程序输出结果:最大公约数为:3

    最小公倍数为:18

    展开全文
  • 用 Java实现 输入两个数 求两个数的最大公约数,如何使用java语言求两个数的最大公约数
  • C语言:求两个数的最大公约数和最小公倍数

    万次阅读 多人点赞 2019-06-19 16:31:03
    C语言:求两个数的最大公约数和最小公倍数 求两个数的最大公约数:“辗转相除法”: 设两数为a和b(a>b),用a除以b,得a÷b=商…余数,若余数为0 ,则最大公约数为b;若余数不为0 ,则再用b÷余数, 得b÷余数=商1...

    C语言:求两个数的最大公约数和最小公倍数

    求两个数的最大公约数:“辗转相除法”:
    设两数为a和b(a>b),用a除以b,得a÷b=商…余数,若余数为0 ,则最大公约数为b;若余数不为0 ,则再用b÷余数,
    得b÷余数=商1…余数1,若余数1=0,则最大公约数为余数,若余数1不为0,继续让商÷余数n,一直到能够余数为零
    这时的除数即最大公约数。
    求两个数的最小公倍数:
    最小公倍数=两数的乘积÷最大公约数

    #include <stdio.h>
    #define MAX(a,b) (a>b)?a:b
    #define MIN(a,b) (a<b)?a:b
    int main()
    {
    	int a,b;
    	int yu;
    	int m,n;
    	printf("input two numbers:\n");
    	scanf("%d,%d", &m, &n);
    	a =MAX(m,n);
    	b= MIN(m,n);
    	while (a%b != 0)
    	{
    		yu = a%b;
    		a = b;
    		b = yu;
    	 }
    	printf("最大公约数为:%d\n", b);
    	printf("最小公倍数为:%d",m*n/b);
    	return 0;
    }
    
    展开全文
  • Python求两个数的最大公约数一、求最大公约数算法:1. 整数A对整数B进行取整, 余数用整数C来表示 举例: C = A % B2. 如果C等于0,则C就是整数A和整数B的最大公约数3. 如果C不等于0, 将B赋值给A, 将C赋值给B ,然后进行 ...

    Python求两个数的最大公约数

    一、求最大公约数算法:

    1. 整数A对整数B进行取整, 余数用整数C来表示 举例: C = A % B

    2. 如果C等于0,则C就是整数A和整数B的最大公约数

    3. 如果C不等于0, 将B赋值给A, 将C赋值给B ,然后进行 1, 2 两步,直到余数为0, 则可以得知最大公约数

    二、根据算法,实现Python程序def fun(num1, num2): # 定义一个函数, 两个形参

    if num1 < num2: # 判读两个整数的大小,目的为了将大的数作为除数,小的作为被除数

    num1, num2 = num2, num1 # 如果if条件满足,则进行值的交换

    vari1 = num1 * num2 # 计算出两个整数的乘积,方便后面计算最小公倍数

    vari2 = num1 % num2 # 对2个整数进行取余数

    while vari2 != 0: # 判断余数是否为0, 如果不为0,则进入循环

    num1 = num2 # 重新进行赋值,进行下次计算

    num2 = vari2

    vari2 = num1 % num2 # 对重新赋值后的两个整数取余数

    # 直到 vari2 等于0,得到最到公约数就退出循环

    vari1 /= num2 # 得出最小公倍数

    print("最大公约数为:%d" % num2) # 输出

    print("最小公倍数为:%d" % vari1) # 输出

    fun(6, 9)

    程序输出结果:最大公约数为:3

    最小公倍数为:18

    推荐:Python教程

    展开全文
  • 今天参加腾讯笔试,做编程题时...2、求两个数的最大公约数(递归法、相减法、辗转相除法) 3、求两个数的最小公倍数,两个数的最小公倍数与它们的最大公约数之间存在如下关系: 某两个数a,b的最小公倍数=(a*b)/a与b...
  • 火山日常啰嗦今天参加腾讯笔试,做...2、求两个数的最大公约数(递归法、相减法、辗转相除法)3、求两个数的最小公倍数,两个数的最小公倍数与它们的最大公约数之间存在如下关系:某两个数a,b的最小公倍数=(a*b)/a与b...
  • 两个数的最大公约数和最小公倍数
  • 穷举法(也叫枚举法)穷举法求两个正整数的最大公约数的解题步骤: 从两个数中较小数开始由大到小列举,直到找到公约数立即中断列举,得到的公...穷举法求两个数的最大公约数代码: import java.util.Scanner; publ
  • 2020-09-22:已知两个数的最大公约数和最小公倍数,并且这两个数不能是最大公约数和最小公倍数本身。如何判断这两个数是否存在?福哥答案2020-09-22:#福大大架构师每日一题#1.如果最小公倍数不能被最大公约数整除,...
  • 本文介绍了使用C#获取两个数的最大公约数和最小公倍数的示例,大家参考使用吧
  • Python求两个数的最大公约数一、求最大公约数算法:1. 整数A对整数B进行取整, 余数用整数C来表示 举例: C = A % B2. 如果C等于0,则C就是整数A和整数B的最大公约数3. 如果C不等于0, 将B赋值给A, 将C赋值给B ,然后进行 ...
  • Python求两个数的最大公约数一、求最大公约数算法:1. 整数A对整数B进行取整, 余数用整数C来表示 举例: C = A % B2. 如果C等于0,则C就是整数A和整数B的最大公约数3. 如果C不等于0, 将B赋值给A, 将C赋值给B ,然后进行 ...
  • 比如我们接下来要说的求两个数的最大公约数的问题。这类简单的算法题目一般会出现在面试环节,面试官要求你当场手撕的那种。言归正传,首先我们要知道面试官出求两个数的最大公约数这个题目的目的是什么。知己知彼,...
  • 1. 求最小公倍数的算法:最小公倍数 = 两个整数的乘积 / 最大公约数所以我们首先要求出两个整数的最大公约数, 求两个数的最大公约数思路如下:2. 求最大公约数算法:1. 整数A对整数B进行取整, 余数用整数C来表示 举例: ...
  • 两个数的最大公约数。 1、思路:先对两个数进行比较大小,以最小的数来求其公约数。判断这些公约数是否能同时被两个数都整数,并选取最大的值作为两个数的公约数。 2、程序: ...
  • 主要介绍了C语言求两个数的最大公约数及最小公倍数的方法,辗转相除法和辗转相减法在解决这种问题时最常用到,需要的朋友可以参考下
  • 两个数的最大公约数的三种算法

    万次阅读 多人点赞 2017-03-22 22:01:04
    辗转相除法:取两个数中最大的数做除数,较小的数做被除数,用最大的数除较小数,如果余数为0,则较小数为这两个数的最大公约数,如果余数不为0,用较小数除上一步计算出的余数,直到余数为0,则这两个数的最大公...
  • C语言怎么样计算两个数的最大公约数和最小公倍数发布时间:2020-12-03 09:51:30来源:亿速云阅读:105作者:小新小编给大家分享一下C语言怎么样计算两个数的最大公约数和最小公倍数,相信大部分人都还不怎么了解,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,718
精华内容 2,687
关键字:

两个数的最大公约数