首页 > 试题广场 >

最大公约数

[编程题]最大公约数

热度指数：38657 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

如果有一个自然数 a 能被自然数 b 整除，则称 a 为 b 的倍数， b 为 a 的约数。几个自然数公有的约数，叫做这几个自然数的公约数。公约数中最大的一个公约数，称为这几个自然数的最大公约数。

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

数据范围： $1 \le a,b \le 10^9$

进阶：空间复杂度 $O(1)$ ，时间复杂度 $O(logn)$

示例1

输入

3,6

输出

示例2

输入

8,12

输出

备注:

a和b的范围是[1-10⁹]

算法知识视频讲解

Java

牛客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)

Java

煎饼狗子6999

int n=Math.min(a,b);

int m=0;

for(int i=n;i>=1;i--){

if(a%i==0&&b%i==0){

m=i;

break;

}

return m;比较适合我们这种大一去写

编辑于 2023-12-16 10:19:14 回复(1)

Java

35岁打螺丝转Java

import java.util.*;

public class Solution {

public int gcd (int a, int b) {

int i = a > b ? b : a;

for(;i > 0;i--){

if((double)a / i % 1 == 0 & (double)b / i % 1 == 0){

return i;

}

return 0;

}

发表于 2023-04-10 19:56:22 回复(0)

Java

zyxjeek

public class Solution {
    public int gcd (int a, int b) {
        // write code here
        if (b == 0) return a;
        return gcd(Math.min(a, b), Math.max(a, b) % Math.min(a, b));
    }

辗转相除递归

发表于 2022-08-13 15:57:25 回复(0)

Java

北晨LPL

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
        if (b == 0) {
            return a;
        }
        
        return a > b ? gcd(b, a % b) : gcd(a, b % a);
    }
}

发表于 2022-07-15 14:11:58 回复(1)

Java

ljc006

    public int gcd (int a, int b) {
        // write code here
        int i = a>b?a:b;
        while(a%i != 0 || b%i != 0){
            i--;
        } 
        return i;
    }

发表于 2022-04-16 11:09:39 回复(0)

Java

玄鉴

JAVA一行

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求出a、b的最大公约数。
     * @param a int 
     * @param b int 
     * @return int
     */
    public int gcd (int a, int b) {
     return a>b?gcd(b,a):b%a==0?a:gcd(b%a,a);
    }
}

发表于 2021-12-23 20:28:34 回复(0)

Java

岳下郎

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
int max = a>=b?a:b;
int min = a<=b?a:b;
return (max%min==0)?min:gcd(min,max%min);
}
}

发表于 2021-12-02 00:27:29 回复(0)

Java

ninghai

枚举法

if (b % a == 0) {
    return a;
}
int minNum = Math.min(a, b);
for (int i = minNum; i >= 1; i--) {
    if (a % i == 0 && b % i == 0) {
        return i;
    }
}
return 0;

辗转相除法（欧几里得法）

欧几里得算法是用来求两个正整数最大公约数的算法。古希腊数学家欧几里得在其著作《The Elements》中最早描述了这种算法,所以被命名为欧几里得算法。计算公式gcd(a,b) = gcd(b,a mod b)。

if(b == 0){
    return a;
}
return gcd(b,a % b);

假如需要求 1997 和 615 两个正整数的最大公约数,用欧几里得算法，是这样进行的：

1997 / 615 = 3 (余 152)

615 / 152 = 4(余7)

152 / 7 = 21(余5)

7 / 5 = 1 (余2)

5 / 2 = 2 (余1)

2 / 1 = 2 (余0)

至此，最大公约数为1

更相减损法

第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。

第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。

则第一步中约掉的若干个2的积与第二步中等数的乘积就是所求的最大公约数。

其中所说的“等数”，就是公约数。求“等数”的办法是“更相减损”法。

int x = 0;
while (a % 2 == 0 && b % 2 == 0) {
    a = a / 2;
    b = b / 2;
    x++;
}
if (a == b) {
    if (x != 0) {
        return a * (int) Math.pow(2, x);
    }
    return a;
}
int max = Math.max(a, b);
int min = Math.min(a, b);
if (x != 0) {
    return gcd(max - min, min) * (int) Math.pow(2, x);
} else {
    return gcd(max - min, min);
}

发表于 2021-11-24 10:08:12 回复(0)

Java

菲尼克斯弗兰克

public class Solution {
    // 辗转相除
    public int *** (int a, int b) {
        if (b == 0) return a;
        return ***(b, a % b);
    }
}

发表于 2021-09-25 16:55:19 回复(0)

Java

牛客434318841号

两种方法，辗转相除法，更相减损法

1.辗转相除法

if (a==0||b==0) return a==0?a:b;
if(a%b==0) return b;
return gcd(b,a%b);

2.更相减损法

if (a<b){     
    int tmp=a;
  a=b;
  b=tmp; }
if (a==0||b==0)return a==0?a:b;
if (a-b==0) return a;
return gcd(b,a-b);

发表于 2021-06-27 03:15:47 回复(0)

Java

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)

Java

惠灵顿靖

辗转相除法（欧几里德法）

    public int gcd (int a, int b) {
        if(a%b==0)return b;
        int res=gcd(b,a%b);
        return res;}

发表于 2021-04-14 19:19:54 回复(0)

Java

靠谱的大魔王练习时长两年半

public int gcd (int a, int b) {
        // write code here
        if(a%b==0||b%a==0)
        {
            return a>b? b:a;
        }
        else
        {    int max=0;
            for(int i=1;i<=(a>b?b:a);i++)
            {
                if(a%i==0&&b%i==0)
                {
                    max=i;
                }
            }
         return max;
        }
        
    }

发表于 2021-04-10 23:55:03 回复(0)

Java

zzZZiii

发表于 2021-04-01 20:02:40 回复(0)

Java

花落梦里

    public int *** (int a, int b) {
       if(a==b) return a;
       if(a>b) return dfs(a,b);
       else return dfs(b,a);
    }
    public int dfs(int big,int small){
        if(big%small==0) return small;
        else return dfs(small,big%small);
    }

发表于 2021-03-31 14:09:51 回复(0)

Java

十四努力进大厂

辗转相除法

发表于 2021-02-24 09:48:35 回复(0)

提交观点

问题信息

基础数学

上传者：牛客301499号

难度：

19条回答 243收藏 3605浏览

通过挑战的用户

查看代码

BUGBOY101

2022-10-10 10:07:05
大白饭的白饭

2022-09-16 11:37:19
牛客57434...

2022-09-16 10:45:22
在攒经验的斑马很纠结

2022-09-16 10:37:24
Flawles...

2022-09-16 10:23:47

最大公约数

输入

输出

输入

输出

备注:

枚举法

辗转相除法（欧几里得法）

更相减损法

问题信息

热门推荐

通过挑战的用户

相关试题