首页 > 试题广场 >

最大公约数

[编程题]最大公约数
  • 热度指数：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]
算法知识视频讲解
添加回答
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)
Python3
小松鼠人来疯头像 小松鼠人来疯 
class Solution:
    def gcd(self, a: int, b: int) -> int:
        if b == 0:
            return a
        else:
            return self.gcd(b, a % b)

发表于 2023-04-19 13:08:03 回复(0)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

最大公约数

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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