问题描述

随机输入两个数，求其最大公约数

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

辗转相除法依赖于一个定理：

两个整数的最大公约数等于其中较小的那个数和两数取模的最大公约数。

即：gcd (x , y) = gcd (y , x % y ) ，其中 x > y。

代码实现

#include <stdio.h>
int main()
{int x,y;scanf("%d%d", &x, &y);while (1){if (x < y)//比较大小，让小的数放在后面{int tmp = x;x = y;y = tmp;}if (x % y == 0)//若余数为 0 则 y 为两数的最大公约数；{printf("最大公约数的 %d\n", y);break;}else//若余数不为 0，则令 x = y，y = 余数，重复循环{int tmp = x % y;x = y;y = tmp;}}return 0;
}

辗转相减法

其原理其实与辗转相除法一样，只是辗转相除法将的是相除取余，而更相减损法讲的是相减取差。

gcd (x , y) = gcd (y , x % y ) ，其中 x > y

代码实现

#include <stdio.h>
int main()
{int x, y;scanf("%d%d", &x, &y);while (1){if (x < y)//比较大小，让小的数放在后面{int tmp = x;x = y;y = tmp;}if (x - y == 0)//若差为 0，则两数相等，它本身就是最大公约数；{printf("最大公约数的 %d\n", y);break;}else//若差不为 0，则令 x = y，y = 差，重复循环{int tmp = x - y;x = y;y = tmp;}}return 0;
}

暴力穷举法

暴击穷举法就是简单粗暴地把 1~ y（前面已经假设 x > y）都列出来分别判断是否为 x、y 的公约数，然后再找到其中最大的一个。

暴力穷举法最大的特点就是简单直接、很容易理解，但是计算比较繁琐。

代码实现

#include<stdio.h>
int gcd(int x, int y)
{int temp = 0;for (temp = x; ; temp--){if (x % temp == 0 && y % temp == 0)break;}return temp;
}
int main()
{int m, n;scanf_s("%d%d", &m, &n);printf("%d", gcd(m, n));return 0;
}

递归法

计算最大公约数gcd(m,n)，用递归形式定义如下：

若m%n等于0，则gcd(m,n)等与n
否则，gcd(m,n)等于gcd(n,m%n)。

用递归方式编写函数gcd(m,n)。编写测试程序求公约数(1,8)、(3,93)、(27,0)、(9885,7651)

代码实现

#include<stdio.h>
int gcd(int m, int n)
{if (m == 0 || n == 0) return 0;else if (m % n == 0) return n;else gcd(n, m % n);
}
int main()
{int m,n;scanf_s("%d%d", &m,&n);printf("%d", gcd(m,n));return 0;
}