求两个数的最大公因数和最小公倍数求两个数的最大公因数和最小

今天看到了一道题，求最大公因数和最小公倍数，这个题要说难不难说简单也不简单，主要就是要看是否掌握求最大公因数和最小公倍数的算法，那么今天我就在这说一下这个题：（代码在最后）
首先不急着写代码，这个题主要点就在于怎么求最大公因数和最小公倍数，所以我们先来分析一下求这两个数的方法，假设这里两个数a,b；下面是我的解题思路：
最大公因数我先随便给ab赋值，我们先来看看这个测试

a=18b=12a%b—— 18%12=6

a=12 b=6a%b—— 12%6=0
这时6是18和12的最大公因数
2.a=32b=8a%b—— 32%8=0
这时8是32和8的最小公因数
3.a=17b=3a%b——17%3=2
a=3b=2a%b——3%2=1
【求两个数的最大公因数和最小公倍数】a=2b=1a%b——2%1=1
a=1b=1a%b——1%1=0 ,
这时1是17和3的最大公因数
相信通过上面三个例子，我们可以找出一些规律，我们总是用大数模小数得到余数，如果余数不等于0，我们将之前的小数当作大数，余数当作小数（我用相同颜色的数表示是从上一个式子中拿来的，这样可以清楚的看到操作步骤），一直模下去，直至余数为0，这时这个小数就是最大公因数。
我们会发现，这上面从一开始就是用a模b，然而如果我们将a的值赋值比b小，那么此算法还可以成立吗？答案是成立的，这里举个例子：
4.a=8b=32a%b——8%32=8
a=32b=8a%b—— 32%8=0
这时8是32和8的最小公因数
这里很明显我们发现，将执行完第一步，就跟上面没有区别了，所以得出此算法依然成立。
最小公倍数这个算法比较好理解了，上面我们已经算出最大公因数了，我们发现两数之积除以最大公因数就可以得到最小公倍数
随便举个例子
5.a=18b=12上面我们已经算出他的最大公因数是6
那么（a*b）/6=（18*12）/6=36
36就是最小公倍数
上面算法已经介绍完毕，直接看代码和结果演示吧

#define _CRT_SECURE_NO_WARNINGS 1 #include int main() { int a = 0; int b = 0; int tmp = 0; int m = 0; printf("请输入两个整数：\n"); scanf("%d%d", &a, &b); m = a * b; while(tmp = a%b) { a = b; b = tmp; } tmp = m / b; printf("最大公因数=%d\n",b ); printf("最小公倍数=%d\n", tmp); system("pause"); return 0; }