使用Euclid算法求最大公约数

╰+哭是因爲堅強的太久メ 2021-11-09 23:58 349阅读 0赞

## 参考文章　 ##

1、《linux c编程一站式学习》的习题5.3.1

2、百度百科Euclid算法：[https://baike.baidu.com/item/Euclid%E7%AE%97%E6%B3%95][https_baike.baidu.com_item_Euclid_E7_AE_97_E6_B3_95]

## 思想 ##

使用Eucid算法编写两个正整数a和b的最大公约数（GCD, Greatest Common Dvisor）

1、如果a能整除b, 则最大公约数是b

2、否则，最大公约数等于b和a%b的最大公约数；即gcd(a,b)=gcd(b,a%b)

## code ##

1 //功能：求取两个正整数的最大公约数
     2 #include <stdio.h>
     3 
     4 //方法1：采用循环，不需要考虑a大还是b大
     5 int gcd1(int a, int b)
     6 {
     7     int r;
     8     while(b > 0){
     9         r = a % b;
    10         a = b;
    11         b = r;
    12     }
    13     return a;
    14 }
    15 
    16 //方法2：采用递归算法
    17 int gcd2(int a, int b)
    18 {
    19     return (b>0) ? gcd2(b, a%b) : a;
    20 }
    21 
    22 
    23 int main(int argc, char *argv[])
    24 {
    25     int a, b, res;
    26     while(1){
    27         printf("please input 2 intergers:\n");
    28         scanf("%d %d", &a, &b);
    29         printf("a=%d, b=%d\n", a, b);
    30         
    31         res = gcd1(a, b);
    32         printf("gcd1: the greatest common divisor of %d and %d is: %d\n", a, b, res);
    33 
    34         res = gcd2(a, b);
    35         printf("gcd2: the greatest common divisor of %d and %d is: %d\n", a, b, res);
    36         
    37     }
    38 }

## 运行结果截图 ##

![663740-20190529145152724-1340007972.png][]

转载于:https://www.cnblogs.com/shanyu20/p/10943853.html

[https_baike.baidu.com_item_Euclid_E7_AE_97_E6_B3_95]: https://baike.baidu.com/item/Euclid%E7%AE%97%E6%B3%95
[663740-20190529145152724-1340007972.png]: /images/20211109/72dbe8c1db7f47fd82e93b765c67d70e.png