首页 > 试题广场 >

最大公约数

[编程题]最大公约数
  • 热度指数：39409 时间限制：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]
算法知识视频讲解
添加回答
Python 3
来牛客玩玩头像 来牛客玩玩 
class Solution:
    def gcd(self , a: int, b: int) -> int:
        # write code here
        while b % a:
            a, b = b%a, a
        return a

发表于 2022-06-19 22:08:16 回复(0)
Python 3
danspace头像 danspace 
class Solution:
    def gcd(self , a: int, b: int) -> int:
        # write code here
        if a%b == 0:
            return b
        return self.gcd(b, a%b)

发表于 2022-04-19 10:07:46 回复(0)
Python 3
Ron1997头像 Ron1997 
class Solution:
    def gcd(self , a: int, b: int) -> int:
        # write code here
        s=min(a,b)
        for i in range(1,s+1):
            if b%(s//i)==0 and a%(s//i)==0:
                return s//i

发表于 2022-03-31 21:07:56 回复(0)
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)
Python 3
Joy_9头像 Joy_9 
class Solution:
    def gcd(self , a: int, b: int) -> int:
        # write code here
        a,b=max(a,b),min(a,b)
        mod=a%b
        while mod!=0:
            a,b=b,mod
            mod=a%b
        return b  

发表于 2022-01-03 23:56:04 回复(0)
Python 3
tangjunjun头像 tangjunjun 
class Solution:
    def gcd(self , a: int, b: int) -> int:
        # write code here
        if b==0:
            return a
        else:
            return self.gcd(b, a%b)

发表于 2021-11-17 23:59:09 回复(0)
Python 3
摆烂远离哥头像 摆烂远离哥
            for n in range(a//2+1,0,-1):
                if a//n>=2 and a%n==0 and b//n>=2 and b%n==0 :
                    return n
#数值过大就会出现运行超时，不知道怎么提高
发表于 2021-11-14 14:20:04 回复(0)
Python 3
JSFaner头像 JSFaner 
class Solution:
    def gcd(self , a: int, b: int) -> int:
        while a > 0:
            tmp = b % a
            b = a
            a = tmp
        return b 

发表于 2021-11-13 19:14:01 回复(0)
Python 3
NEWTON头像 NEWTON 
class Solution:
    def gcd(self , a , b ):
        # write code here
        if a<b:
            a,b=b,a
        while(a%b!=0):
            a,b=b,a%b
        return b    
        
        

发表于 2021-10-19 00:37:07 回复(0)
Python 3
榴莲不留恋头像 榴莲不留恋
啊啊啊我第一个写出来的，开心~
虽然很简单哈哈，用的是辗转相除法。同时最小公倍数用最大公因数就可以算出来啦~~ 
class Solution:
    def gcd(self , a , b ):
        # write code here
        while 1:
            c=a%b 
            if c==0:
                return b
            else:
                a=b 
                b=c 


发表于 2021-10-15 22:58:43 回复(0)
Python 3
牛客680328616号头像 牛客680328616号 
class Solution:
    def gcd(self , a , b ):
        # write code here
        if a > b:
            max_ = a
        else:
            max_ = b
        for i in range(1,max_+1):
            if a % i == 0 and b % i == 0:
                aa = i
        return aa

发表于 2021-09-03 14:43:33 回复(0)
Python 3
牛客725251878号头像 牛客725251878号
class Solution:
    def gcd(self , a , b ):
        c=[]
        d=[]
        if a>=b:
            for i in range(1,b+1):
                if a%i==0 and b%i==0:
                    c.append(i)
            return max(c)
        elif b>=a:
            for j in range(1,a+1):
                if a%j==0 and b%j==0:
                    d.append(j)
            return max(d)
发表于 2021-09-01 03:40:20 回复(0)
Python 3
Demo_mo头像 Demo_mo
class Solution:
    def gcd(self , a , b ):
        # write code here
        temp = 1
        for i in range(2,min(a,b)+1):
            if int(a%i) == 0 and int(b%i) == 0:
                temp = i
        return temp

运行超时:您的程序未能在规定时间内运行结束，请检查是否循环有错或算法复杂度过大.
285406331,25728026
1
哎，算法逻辑简单，但是运行效率很低
发表于 2021-08-28 09:29:13 回复(1)
Python 3
Stephenling头像 Stephenling
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 求出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
#         除法求余
        print('a=',a,'b=',b)
        while b!=0:
            a,b = b,a%b
            print('a=',a,'b=',b)
        return a
发表于 2021-08-10 21:59:45 回复(0)
Python 3
Jingle_xu头像 Jingle_xu 
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 求出a、b的最大公约数。
# @param a int 
# @param b int 
# @return int
#
class Solution:
    def gcd(self , a , b ):
        # write code here
        # 辗转相除法, 两数取余，若余数为0，则该除数为最大公约数
        # 否则，继续将除数与余数取余
#         s = a % b
#         if s == 0:
#             return b
#         else:
#             return self.gcd(b, a % b)
        #更相减损法， 大的数减去小的数，若差值等于小的数，则该值为最大公约数
        # 否则，刚刚小的数，和差值继续上述流程
        while b:
            if a < b:
                a, b = b, a
            a, b = b, a-b
        return a
#                暴力法，超时
#         if a >= b:
#             big = a
#             small = b
#         else:
#             big = b
#             small = a
#         for i in range(small+1, 0, -1):
#             if big % i == 0 and small % i == 0:
#                 return i

发表于 2021-07-22 21:15:16 回复(0)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

最大公约数

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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