求最大公约数的几种算法

求两个数的最大公约数是生活中常见的运算。我们普遍知道的有欧几里得法、穷举法，其实还有其它方法：更相减损法。下面面一起来看看：

1、辗转相除法，又叫欧几里得法：
int f1(int n1, int m1)//最大公约数子函数 { int n = n1 > m1 ? n1 : m1; int m = n1 < m1
? n1 : m1; if (n % m == 0)//能直接相除的情况 { return m; } else { while (m) { int r = n
% m; n = m; m = r; } return n; } } int main() { printf("输入两个数：\n"); int n=0, m
= 0; scanf("%d%d", &n,& m); int max = f1(n, m); printf("最大公约数是 %d\n", max);
return 0; }
运行结果：

2、递归：
int f1(int n1, int m1)//最大公约数子函数 { int n = n1 > m1 ? n1 : m1; int m = n1 < m1
? n1 : m1; if (n % m == 0)//能直接相除的情况 { return m; } else { return f1(m, n%m); }
} int main() { printf("输入两个数：\n"); int n=0, m = 0; scanf("%d%d", &n,& m); int
max = f1(n, m); printf("最大公约数是 %d\n", max); return 0; }
 运行结果：

3、更相减损法：
int f1(int n1, int m1)//最大公约数子函数 { int n = n1 > m1 ? n1 : m1; int m = n1 < m1
? n1 : m1; if (n % m == 0) return m; else { return f1(m, n - m); } } int main()
{ printf("输入两个数：\n"); int n=0, m = 0; scanf("%d%d", &n,& m); int max = f1(n,
m); printf("最大公约数是 %d\n", max); return 0; }
 运行结果：

 4、穷举法：
int f1(int n1, int m1)//最大公约数子函数 { int n = n1 > m1 ? n1 : m1; int m = n1 < m1
? n1 : m1; int i = 0; for (i=m; i >= 1; i--) { if (n % i == 0 && m % i == 0) {
return i; break; } } return 1; } int main() { printf("输入两个数：\n"); int n=0, m =
0; scanf("%d%d", &n,& m); int max = f1(n, m); printf("最大公约数是 %d\n", max);
return 0; }

 

四种算法各自有自己的优点。

• « 上一篇：App防止网络请求被代理抓包的解决方法
• » 下一篇：Vue3中vuex的基本使用