首页 > 试题广场 >

最大公约数

[编程题]最大公约数
  • 热度指数：39404 时间限制：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]
算法知识视频讲解
添加回答
Javascript
ZoeNull头像 ZoeNull
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 求出a、b的最大公约数。
 * @param a int 
 * @param b int 
 * @return int
 */
function gcd( a ,  b ) {
    // write code here
    var a1 = [];
let min= Math.min(a,b)
        for (let i = min ;i > 0 ;i--){
            if(a%i == 0 && b%i ==0){
                return i
            }
        }

}
module.exports = {
    gcd : gcd
};
发表于 2022-03-27 19:57:36 回复(0)
Javascript
FoRtCurious头像 FoRtCurious
js必须要有答案
function gcd( a ,  b ) {
    // write code here
    if (a%b === 0 || b%a ===0) return Math.min(a,b);
    return b===0 ? a : gcd(b,a%b);
}
发表于 2021-12-10 20:17:56 回复(0)
Javascript
牛客824893881号头像 牛客824893881号
JavaScript版：
function gcd( a ,  b ) {
    let min = Math.min(a,b)
    for(let i = min;i>=1;i--){
        if(a%i==0 && b%i==0){
            return i
        }
    }
}
发表于 2021-10-22 18:14:12 回复(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)
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)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

最大公约数

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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