给定两个数,求这两个数的最大公约数

简介: 给定两个数,求这两个数的最大公约数

给定两个数,求这两个数的最大公约数
例如:
输入:40 20
输出:20

最大公约数:即两个数据中公共约束的最大者,而求解的方式也很多,例如:

暴力穷举,辗转相除法,更相减损法,Stein算法算法

在这里我们先用辗转相除法来求解这道题目

举例:40和20的最大公约数

第一次:a = 40 b =20 c = a%b = 40%20= 0

循环结束

此时b中的内容即为两个数中的最大公约数。

int main()
{
  int a = 0;
  int b = 0;
  int c = 0;
  scanf("%d%d", &a, &b);
  while (c = a % b)
  {
    a = b;
    b = c;
  }
  printf("%d\n", b);
  return 0;
}

结果:

相关文章
|
2月前
求这两个数的最大公约数
【10月更文挑战第21天】求这两个数的最大公约数。
14 1
|
7月前
10.输入一个数,求这个数的阶乘
10.输入一个数,求这个数的阶乘
35 0
|
7月前
|
算法 测试技术 C#
【最大公约数 调和级数】2183.统计可以被 K 整除的下标对数目
【最大公约数 调和级数】2183.统计可以被 K 整除的下标对数目
|
算法 C语言
自守数算法
自守数算法
78 0
|
索引
三个数的最大乘积
三个数的最大乘积
71 0
|
Python
找几个数的最大乘积
找几个数的最大乘积
75 0
|
机器学习/深度学习
欧拉函数:求小于等于n且与n互质的数的个数
求小于等于n且与n互质的数的个数 互质穷举法 互质:两个数互质代表两者最大公约数为1 最大公约数求法:辗转相除法,最小公倍数:较大值除以最大公约数乘以较小值 辗转相除法: 较大的数a取模较小的数b,得取模值c 若取模值等于0 则最大公约数为取模值,否则继续下一步 a与c再次取模,回到第二步 //求最大公约数gcd以及最大公倍数lcm // 36 24 36/24 // 24 12 24/12 // 0 结束最大公约数为12 // 求最小公倍数 // lcm(a, b) = (a * b)/g
152 0
|
机器学习/深度学习 算法 Windows
HOW求两个数的最大公约数?
HOW求两个数的最大公约数?
117 0
HOW求两个数的最大公约数?
给你一组数,求出其中两两最大公约数中最大的值
给你一组数,求出其中两两最大公约数中最大的值
67 0