首页 > 试题广场 >

最大公约数

[编程题]最大公约数
  • 热度指数：40085 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
如果有一个自然数 a 能被自然数 b 整除，则称 a 为 b 的倍数， b 为 a 的约数。几个自然数公有的约数，叫做这几个自然数的公约数。公约数中最大的一个公约数，称为这几个自然数的最大公约数。

输入 a 和 b , 请返回 a 和 b 的最大公约数。

数据范围：
进阶：空间复杂度 ，时间复杂度
示例1

输入

3,6

输出

3
示例2

输入

8,12

输出

4

备注:
a和b的范围是[1-109]
算法知识视频讲解
添加回答
嘚头像 嘚 
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 求出a、b的最大公约数。
# @param a int 
# @param b int 
# @return int
#
class Solution:
    def gcd(self , a , b ):
#         print(a,b)
        # write code here
        if a < b: #保证 a>b
            tmp = a 
            a = b
            b = tmp
#             print(a,b)
        c = a % b
        if c == 0:
            return b
        else:
            return self.gcd(b,c)
更相减损法
发表于 2021-09-11 14:59:58 回复(0)
Java
ChinaZhou头像 ChinaZhou 
import java.util.*;


public class Solution {

    public int gcd (int a, int b) {
        int i;
        if(a>b){
            i = b;
        }else{
            i = a;
        }
        for(;i>0;i--){
            if (a % i ==0 && b % i ==0){
                return i;
            }
        }
        return 0;
    }
}
来自一个小白的解题过程。
发表于 2021-06-17 16:32:55 回复(0)
JavaScript
别卷啦！头像 别卷啦！
辗转相除法： 
function ***( a ,  b ) {
    // write code here 
		let temp=0;
		while(b!=0){		//b==0时,a为最大公约数
			temp=a%b;
			a=b;
			b=temp;
		}
		return a;
	
}
优化版本： 
function ***( a ,  b ) {
    // write code here
    return b!=0 ? ***(b,a%b) : a


编辑于 2021-01-15 17:05:10 回复(0)
风林小牛头像 风林小牛
说明都在注释里 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求出a、b的最大公约数。
     * @param a int 
     * @param b int 
     * @return int
     */
    public int *** (int a, int b) {
        // write code here
        
        //方法1：暴力枚举
//         int min = a < b ? a : b;
//         for(int i = min;i >= 1;i--){
//             if(a % i == 0 && b % i == 0){
//                 return i;
//             }
//         }
//         return 0;
        
        //方法2：暴力枚举法优化
//         int max = a > b ? a : b;
//         int min = a < b ? a : b;
//         if(max % min == 0) return min;
//         for(int i = min / 2;i >= 1;i--){
//             if(a % i == 0 && b % i == 0){
//                 return i;
//             }
//         }
//         return 0;
        
        //方法3：辗转相除法
//         int max = a > b ? a : b;
//         int min = a < b ? a : b;
//         if(max % min == 0) return min;
//         return ***(max % min, min);
        
        
        //方法4：更相减损术（避免了取模运算，用效率更高的减法运算替代）
//         int max = a > b ? a : b;
//         int min = a < b ? a : b;
//         if(max % min == 0) return min;
//         return ***(max - min, min);
        
        //方法5：更相减损术非递归实现
        while(a != b){
            if(a > b) a -= b;
            else b -= a;
        }
        return a;
        
        //方法6:3与4相结合
        //3的缺点在于取模运算效率低下，4的缺点在于减法运算次数增加
        //将二者结合，取其精华，去其糟粕
//         if(a == b) return a;
//         if((a & 1) == 0 && (b & 1) == 0){
//             return ***(a >> 1, b >> 1) << 1;
//         }else if((a & 1) == 0 && (b & 1) != 0){
//             return ***(a >> 1, b);
//         }else if((a & 1) != 0 && (b & 1) == 0){
//             return ***(a, b >> 1);
//         }else {
//             int max = a > b ? a : b;
//             int min = a < b ? a : b;
//             return ***(min, max - min);
//         }
    }
}


发表于 2021-03-01 16:38:35 回复(0)
漫漫云天自翱翔头像 漫漫云天自翱翔 
return (a%b==0)?b:gcd(b,a%b);


发表于 2021-02-25 16:15:46 回复(0)
wengJJ头像 wengJJ
Python
学习了减法和除法的方法足以面对面试了 
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 求出a、b的最大公约数。
# @param a int 
# @param b int 
# @return int
#
class Solution:
    def gcd(self , a , b ):
        # write code here
#         减法
#         while a!=b :
#             if(a>b): 
#                 a=a-b
#             else: 
#                 b=b-a
#         return a
#         除法求余
        while b!=0:
            a,b = b,a%b
        return a
        


发表于 2021-04-15 15:30:23 回复(0)
C++
忧亭落雨阁头像 忧亭落雨阁
递归： 
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求出a、b的最大公约数。
     * @param a int 
     * @param b int 
     * @return int
     */
    int gcd(int a, int b) {
        // write code here
        if (b % a == 0) return a;
        return gcd(b % a, a);
    }
};


发表于 2021-11-11 16:43:12 回复(1)
Python 3
江西南昌陈彬头像 江西南昌陈彬

# 只要循环10 次就能出准确结果，，速度超快，
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 求出a、b的最大公约数。
# @param a int整型 
# @param b int整型 
# @return int整型
#
class Solution:
    def gcd(self , a: int, b: int) -> int:
        # write code here
        cg = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
        maxs = 0
        a_c = 0
        if b % a == 0:
            maxs = a
            return maxs
        elif a % b == 0:
            maxs = b
            return maxs
        else:
            import re
            try:
                a_lin = str(re.findall(r'[0]+$', str(a))[0])
                b_lin = str(re.findall(r'[0]+$', str(b))[0])
            except:
                a_lin = ''
                b_lin = ''
            if len(a_lin) >= 1 and len(b_lin) >= 1:
                if len(a_lin) >= len(b_lin):
                    lin = '0' * len(b_lin)
                else:
                    lin = '0' * len(a_lin)
                a = int(re.sub(r'[0]+$', "", str(a)).strip() + '0' * (len(a_lin) - len(lin)))
                b = int(re.sub(r'[0]+$', "", str(b)).strip() + '0' * (len(b_lin) - len(lin)))
                while a_c < len(cg):
                    y = a % cg[a_c]
                    x = b % cg[a_c]
                    if y == 0 and x == 0:
                        if cg[a_c] > maxs:
                            maxs = cg[a_c]
                    ya = a / cg[a_c]
                    if b % ya == 0:
                        if ya > maxs:
                            maxs = ya
                    a_c += 1
                print(int(str(int(maxs)) + str(lin)))
                return int(str(int(maxs)) + str(lin))
            else:
                while a_c < len(cg):
                    y = a % cg[a_c]
                    x = b % cg[a_c]
                    if y == 0 and x == 0:
                        if cg[a_c] > maxs:
                            maxs = cg[a_c]
                    ya = a / cg[a_c]
                    if b % ya == 0:
                        if ya > maxs:
                            maxs = ya
                    a_c += 1
                print(maxs)
                return int(maxs)
发表于 2022-02-08 12:46:38 回复(0)
JavaScript
IPzzzi头像 IPzzzi 
function gcd( a ,  b ) {
    // write code here
    if(a%b == 0){
        return b;
    }else{
        return gcd(b,a%b);
    }
}

发表于 2021-04-24 11:47:16 回复(2)
JavaScript
SharkPerry头像 SharkPerry 
if(a%b ==0 || b%a ==0) return a%b==0?b:a;
    while(a!=b){
        if(a>b) a=a-b;
        else b=b-a;
    }
    // 返回b和返回a是一样的效果
    return b
看到大佬的思路才知道需要循环相减，知道两数最后相等才推出循环，加油打工人
发表于 2021-04-13 21:32:16 回复(1)
Carlos_z头像 Carlos_z 
# 辗转相减法求最大公约数
class Solution:
    def gcd(self , a , b ):
        # write code here
        while a != b:
            if a > b:
                a = a - b 
            else:
                b = b - a
        return a

编辑于 2021-04-05 11:26:21 回复(0)
唐氏综合征头像 唐氏综合征
1. 假设  a > b， a 可以拆分为 n 个b + 余数，即 a = n*b + left
2. 然后求解最大公约数的时候， a 按 b 可最少拆分为了  {b,b,b,b, ... , lelft}，因此，a 与 b 的最大公约数应该是每个拆分项与 b 的相同公约数的最大值，因为只有这样才能抵消掉， 因为 b 与 b 的最大公约数是它本身， 因此只需要考虑 left 与 b 的最大公约数即可，代码如下：
  public static int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }


注意点：理论上 a 应该比 b 大，但代码没判断，因为如果 a < b， 那么在下一轮循环中也会把位置互换过来
发表于 2024-07-05 12:40:51 回复(0)
C
Dyer不是呆鹅头像 Dyer不是呆鹅
 /*
-->如果b = 0，计算结束，则a就为最大公约数<--
否则，计算a%b的余数，让b的值赋值给a，而b赋值为那个余数
最后，返回第一步
  a    b    t
  12   18   12
  18   12   6
  12   6    0
  6    0
  
  
 */
intgcd(inta, intb ) {
    // write code here
    intt;
    while(b != 0){
        t = a%b;
        a =b;
        b =t;
    }
    returna;
}
发表于 2023-09-17 19:18:17 回复(0)
C
cyb99头像 cyb99
int gcd(int a, int b ) {
    int c;
    while(a%b)
    {
        c = b;
        b = a%b;
        a = c;
    }
    return b;
}

辗转相除法，怎么样可以快一点？
发表于 2021-11-01 20:26:44 回复(0)
哈皮李不清头像 哈皮李不清
 求最大公约数 辗转相除法(欧几里德算法) 例如，求（319，377）： ∵ 319÷377=0（余319）
      ∴（319，377）=（377，319）； ∵ 377÷319=1（余58） ∴（377，319）=（319，58）； ∵
      319÷58=5（余29） ∴ （319，58）=（58，29）； ∵ 58÷29=2（余0） ∴ （58，29）= 29； ∴
      （319，377）=29。 可以写成右边的格式。
      用辗转相除法求几个数的最大公约数，可以先求出其中任意两个数的最大公约数，再求这个最大公约数与第三个数的最大公约数，依次求下去，直到最后一个数为止。
      最后所得的那个最大公约数，就是所有这些数的最大公约数。
编辑于 2021-02-24 17:14:34 回复(0)
任酒头像 任酒
  int gcd(int a, int b) {
        // write code here
        if (b%a==0){
           return a;
        }
else{
b=a;
a=b%a;
return gcd(a,b);
}
       
    }
};
发表于 2024-10-07 18:52:28 回复(0)
牛客970627362号头像 牛客970627362号
class Solution:
    def gcd(self , a: int, b: int) -> int:
        # write code here
        if a == b:
            return a
        if a>b:
            big = a
            small = b
        else:
            big = b
            small = a
        mid = 0
        while big-small > 0:
            mid = big - small
            if mid > small:
                big = mid
            else:
                big = small
                small = mid
       
        return mid
发表于 2024-06-30 17:14:52 回复(0)
Python3
liangzhengjie头像 liangzhengjie 
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 求出a、b的最大公约数。
# @param a int整型 
# @param b int整型 
# @return int整型
#
class Solution:
    def gcd(self , a: int, b: int) -> int:
        # write code here
        the_a = max(a, b)
        the_b = min(a, b)

        while the_a%the_b != 0:
            res = the_a%the_b
            the_a,the_b = the_b,res

        return the_b
辗转相除法
编辑于 2024-03-31 00:17:35 回复(0)
Java
牛客839384289号头像 牛客839384289号 
    public int gcd (int a, int b) {
        // write code here
        int num=Math.min(a,b) ,temp=num ,index=1;
        while(temp>1){
            temp=num/index++;
            if(a%temp==0 && b%temp==0){
                break;
            }
        }
        return temp;
// ---------------------------------------------------------------
        if(a%b==0){
            return b;
        }
        return gcd(b ,a%b);
    }

发表于 2024-03-24 15:36:07 回复(0)
牛客2024007号头像 牛客2024007号 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求出a、b的最大公约数。
     * @param a int整型 
     * @param b int整型 
     * @return int整型
     */
    public int gcd (int a, int b) {
        // write code here
        // gcd(a, b) = gcd(b, a % b)
        // 任意整数和0的公约数是该整数的所有约数
        // 它们的最大公约数为该整数本身
        // 记公式就好
        return (b == 0) ? a : gcd(b, a % b);
    }
}

编辑于 2024-02-10 16:28:16 回复(0)
提交观点

问题信息

基础数学
上传者：牛客301499号
难度：
84条回答 4983浏览

热门推荐

通过挑战的用户

查看代码

相关试题

最大公约数

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号