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

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

给定两个数,求这两个数的最大公约数
例如:
输入: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;
}

结果:

相关文章
|
1月前
|
Python
如何判断一个数是质数? 要求:编写一个Python函数,输入一个整数,输出该整数是否为质数。质数是指大于1的自然数中,除了1和它本身以外不再有其他因数的数。
如何判断一个数是质数? 要求:编写一个Python函数,输入一个整数,输出该整数是否为质数。质数是指大于1的自然数中,除了1和它本身以外不再有其他因数的数。
|
1月前
|
算法 测试技术 C#
【最大公约数 调和级数】2183.统计可以被 K 整除的下标对数目
【最大公约数 调和级数】2183.统计可以被 K 整除的下标对数目
|
8月前
|
程序员
【牛客网】HJ99 自守数、OR86 返回小于 N 的质数个数
目录 HJ99 自守数 OR86 返回小于 N 的质数个数
63 0
|
9月前
|
算法 C语言
自守数算法
自守数算法
54 0
|
10月前
wustojc4001判断水仙花数
wustojc4001判断水仙花数
37 0
判断数的奇偶性
判断数的奇偶性
56 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
94 0
HOW求两个数的最小公倍数?
HOW求两个数的最小公倍数?
109 0
HOW求两个数的最小公倍数?
|
机器学习/深度学习 算法 Windows
HOW求两个数的最大公约数?
HOW求两个数的最大公约数?
79 0
HOW求两个数的最大公约数?
统计正数和负数的个数然后计算这些数的平均值(循环、数组解法)
统计正数和负数的个数然后计算这些数的平均值(循环、数组解法)
148 0