函数求最大公约数和最小公倍数 含简单方法（C语言）

解题思路:

一个定理：最大公约数和最小公倍数的乘积就是原来两个数的乘积，因此先计算出简单的最小公倍数，再利用定理就可以得到最小公倍数

本题也包含一般做法，即如何正确的求出最大公约数

注意事项:

①变量名称尽量代表实际意义，编程时要养成这样的好习惯。gcd是最大公约数（greatest common divisor），lcm是最小公倍数（least common multiple）

algorithm意为“算法”

②使用函数需要先在主函数中声明，在外部进行定义。

参考代码:

①简单方法：

#includeint main()
{
	int a,b,gcd,lcm;
	scanf("%d %d",&a,&b);
	for(lcm=1;;lcm++){//使用for循环，思想是让最小公倍数从1开始循环，直到能够同时整除a和b为止
	if(lcm%a==0&&lcm%b==0){
	        break;//此时跳出循环
	    }
	}
	gcd=a*b/lcm;//根据定理很容易得到最大公约数
	printf("%d %d",gcd,lcm);
	return 0;
}

②进阶方法：函数

要求到最大公约数，需要用到短除法：将原来的a和b相除（此时a必须是较大的一个值），b再除以得到的余数，如此递归，最后返回当余数为0时的除数，这个除数就是最大公约数

用4和6来验证：

6%4=2

4%2=0（此时除数为0,2即是4和6的最大公约数）

也可以用较大的两个数进行验证

#includeint main()
{
	int a,b,gcd,lcm;
	scanf("%d %d",&a,&b);
	int algorithm(int x,int y);//决定使用一种较为官方的算法，使用函数进行，先看它的定义
	int x,y;
	x=a>b?a:b;//这两句是实现短除法的前提条件，即保证x>y
	y=a>b?b:a;
	gcd=algorithm(x,y);//调用求最大公约数的算法并把结果给gcd
	lcm=a*b/gcd;//定理求最小公倍数
	printf("%d %d",gcd,lcm);
	return 0;
}
int algorithm(int x,int y){
    if(x%y!=0)
    {
        int c=x%y;//定义一个变量来存放新的除数
        algorithm(y,c);//递归，即y对c取余
    }
    else return y;//此时x对y取余余数为0，返回除数y
}

一定要多多上手实践哦！