首页 > 试题广场 >

最大公约数

[编程题]最大公约数

热度指数：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⁹]

算法知识视频讲解

叶同学的刷题日记

-->如果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)

拧螺丝很喜欢飞来飞去

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

发表于 2022-10-04 18:52:05 回复(0)

337845818

int gcd(int a, int b) {
    // write code here
    int i;
    if (a > b) {
        int t;
        t = a;
        a = b;
        b = t;
    }
    for (i = a; i > 0; i--) {
        if (b % i == 0 && a % i == 0) {
            return i;
        }
    }
    return 0;
}

发表于 2022-06-30 23:16:12 回复(0)

Hao_XL

int gcd(int a, int b )

{

    int c = 1;
    while (c=a%b)
    {
        a = b;
        b = c;
    }
    return b;
}

发表于 2021-12-21 01:07:17 回复(0)

谢谢你送花给我

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 求出a、b的最大公约数。
 * @param a int 
 * @param b int 
 * @return int
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
int gcd(int a, int b ) {
    // write code here
    int t,c;
    if(a<b){
    t=a;
    a=b;
    b=t;
    }
    c=a%b;
    while(c!=0){
        a=b;
        b=c;
        c=a%b;
    }
    return b;
}

发表于 2021-11-26 14:43:14 回复(0)

牛客40918255号

int gcd(int a, int b ) {
    // write code here
    int max=0,min=0,ret=0,i=0;
    if(a>b){
        max=a;
        min=b;
    }else{
        max=b;
        min=a;
    }
    if(b%a==0){
        ret=min;
    }else{
        for(i=0;i<min;i++){
            if(max%(min-i)==0 && min%(min-i)==0){
                ret=min-i;
                break;
            }
        }
    }

    return ret;
}

发表于 2021-11-04 23:55:07 回复(0)