今天看到了一道题,求最大公因数和最小公倍数,这个题要说难不难说简单也不简单,主要就是要看是否掌握求最大公因数和最小公倍数的算法,那么今天我就在这说一下这个题:(代码在最后)

    首先不急着写代码,这个题主要点就在于怎么求最大公因数和最小公倍数,所以我们先来分析一下求这两个数的方法 ,假设这里两个数a,b;下面是我的解题思路:

最大公因数  我先随便给ab赋值,我们先来看看这个测试

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

         a=12 b=6           a%b—— 12%6=0

         这时6是18和12的最大公因数

    2.  a=32   b=8         a%b—— 32%8=0  

         这时8是32和8的最小公因数

    3.  a=17   b=3         a%b——17%3=2

          a=3   b=2          a%b——3%2=1  

          a=2   b=1          a%b——2%1=1

          a=1   b=1          a%b——1%1=0 ,

这时1是17和3的最大公因数

     相信通过上面三个例子,我们可以找出一些规律,我们总是用大数模小数得到余数,如果余数不等于0,我们将之前的小数当作大数,余数当作小数(我用相同颜色的数表示是从上一个式子中拿来的,这样可以清楚的看到操作步骤),一直模下去,直至余数为0,这时这个小数就是最大公因数。   

      我们会发现,这上面从一开始就是用a模b,然而如果我们将a的值赋值比b小,那么此算法还可以成立吗?答案是成立的,这里举个例子:

     4.a=8   b=32          a%b——8%32=8

        a=32   b=8         a%b—— 32%8=0

        这时8是32和8的最小公因数

这里很明显我们发现,将执行完第一步,就跟上面没有区别了,所以得出此算法依然成立。

最小公倍数 这个算法比较好理解了,上面我们已经算出最大公因数了,我们发现两数之积除以最大公因数就可以得到最小公倍数

         随便举个例子

     5.a=18   b=12            上面我们已经算出他的最大公因数是6

                                       那么(a*b)/6=(18*12)/6=36

                                        36就是最小公倍数

上面算法已经介绍完毕,直接看代码和结果演示吧

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
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;
}

声明:本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。