最大公约数的求法

时间:2024-03-08 07:10:11

最大公约数,也称最大公因数、最大公因子,指两个或多个整数共有约数中最大的一个。解法有很多,现在来总结一下:

1、穷举法

这是暴力的方法,即选择两个数中较小的一个作为遍历的范围大小。然后从1开始遍历,判断同时满足是两个数的因子的数有哪些,然后求出最大值即可。

2、更相减损法

这个思想起源于我国古代的《九章算术》,它原本是为约分而设计的,但它适用于任何需要求最大公约数的场合。原文是这么描述的:“可半者半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也。以等数约之。”

翻译成白话将就是:

第一步:对于任意给定的两个正整数a、b,要求出他们的最大公约数,首先判断他们俩是否都是偶数(能被2整除),如果都是偶数则一直除以2约简,直至不能再被2整除,while(a%2==0 && b%2==0){a = a/2;,b=b/2;};

第二步:如果不是,那么就执行下一步,即用较大的数减去较小的数,然后将所得的差值赋值给原先拥有较大值的那个变量,再拿这个变量与较小值的那个变量进行比较,继续用二者中较大的减去较小的,直到两个变量相等;

最后,将第一步约简掉的2依次乘以第二步得到的“等数”就是最大公约数。算法实现代码如下:

public int gcd_num2(int a,int b){   
    while (a!=b){
         if (a>b){
             a = a-b;
         }else {
             b = b-a;
         }
      }
      return a;
    }

 

3、辗转相除法

辗转相除法:辗转相除法是求两个自然数的最大公约数的一种方法,也叫欧几里德算法。对于任意给定的两个正整数,假设a>b,那么先判断b是否为0,如果为0,则最大公约数直接就是a,如果不为0,就将两个整数a与b进行相除,如果余数为0(a%b==0),则b为两数的最大公约数;如果不等于0,则将b赋值给a,将余数赋值给b,再对新的a、b进行递归运算求最大公约数,递归的结束条件就是b==0。

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

 

参考自:百度百科

    CyC2018