目录
1. 求最大公约数
1.1第一种方法 暴力求解
这种方法是最容易想到的，下面看一下思路，比如说找16 18 最大公约数
取到两个数，先判断大小，将小的拿出来。然后用小的这两个数进行取模运算。如果不是对这个取出来的数“–”
1.2 第二种方法 辗转相除法
这种方法也是最不容易想到的，但却是比暴力求解更有效率的一种方法，下面看一下原理
不用对两个数判断大小，直接取模，如果不为零执行while中的语句，将m赋值给n，然后将取模后的数字，赋值给m，这样循环下来，当模为零时跳出来 ，max就是最大公约数
1.3 第三种方法 相减法
最大公约数还有这样一种性质
所以我们可以根据这个性质来 ，求最大公约数
#include <stdio.h>
int main()
{
int a = 0;
int b = 0;
scanf("%d%d",&a,&b);
while(a!=b)
{
if(a>b)
a = a - b;
if(a<b)
b = b - a;
}
printf("%d\n",a);
return 0;
}2.求最小公倍数
2.1 第一种方法 暴力求解
和前面的求最大公约数方法基本一样
2.2 第二种方法 在最大公约数的基础上求
3.看一个牛客网上的练习题
链接 小乐乐与欧几里得_牛客题霸_牛客网 (nowcoder.com)
我们直接用辗转相除法来做
int main()
{
long long n, m;
long long max = 0, min = 0, tmp = 0;
scanf("%lld %lld\n", &n, &m);
//最大公约数
long long a = n, b = m;
while (tmp = n % m)
{
n = m;
m = tmp;
}
max = m;
//最小公倍数
min = a * b / max;
printf("%lld\n", min + max);
return 0;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/91288.html
