河谷川

用户名：bone19871215

访问量：5856

签　名：

等　　级
排　　名	5723
经　　验	1503
参赛次数	0
文章发表	27
年　　龄	33
在职情况	在职
学　　校
专　　业

　　自我简介：

TA的其他文章

[编程入门]选择排序-题解（C语言代码）
浏览：188

你可能喜欢

[编程入门]最大公约数与最小公倍数-题解（C语言代码）_更相减损法

　　作者: 河谷川　　　　发表时间：2020-05-14 14:27:43 浏览：188　|　评论：0　

原题链接：[编程入门]最大公约数与最小公倍数

```c
/*
	更相减损法
	第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。
	第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。
	则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。
*/

#include <stdio.h>
#include <math.h>

int gcf(int, int);		//更相减损法
int lcm(int, int);		//最小公倍数，公式法：最小公倍数=两个数的乘积/最大公约数

int main()
{
	int num1;
	int num2;

scanf("%d %d",&num1,&num2);

printf("%d %d", gcf(num1, num2), lcm(num1, num2));
	   
	return 0;
}

int gcf(int num1, int num2)
{
	int temp;
	int n = 0;			
	int gcd;				//最大公约数
	int quotient = 0;		//商

/*
		判断两个数是否都是偶数。如果是，则用2约简
	*/
	while (num1 % 2 == 0 && num2 % 2 == 0)
	{
		num1 = num1 / 2;
		num2 = num2 / 2;
		n++;				//统计约简的次数
	}

/*
		用较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数，直到所得的减数和差相等为止。
	*/
	do
	{
		gcd = quotient;
		if (num1 > num2)
		{
			temp = num1;
			num1 = num2;
			num2 = temp;
		}
		quotient = num2 - num1;
		num2 = num1;
		num1 = quotient;
	} while (quotient != 0);

/*
		约掉的若干个2与等数的乘积就是所求的最大公约数
	*/

return gcd * pow(2, n);
}

int lcm(int num1, int num2)
{
	return num1 * num2 / gcf(num1, num2);
}
```

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

河谷川

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

C二级辅导-温度转换（C语言代码）

不容易系列2 （C语言代码）

C语言训练-自守数问题（C语言代码） long long

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

[编程入门]最大公约数与最小公倍数-题解（C语言代码）_更相减损法

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

数组输出（C语言代码）--此题的题目描述有问题

简单的a+b （C语言代码）

字符串的输入输出处理（C语言代码）

【计算两点间的距离】（C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

DNA （C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

1051（奇了怪了）

河谷川

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

C二级辅导-温度转换 （C语言代码）

不容易系列2 （C语言代码）

C语言训练-自守数问题 （C语言代码） long long

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

[编程入门]最大公约数与最小公倍数-题解（C语言代码）_更相减损法

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

数组输出 （C语言代码）--此题的题目描述有问题

简单的a+b （C语言代码）

字符串的输入输出处理 （C语言代码）

【计算两点间的距离】 （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

DNA （C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

1051（奇了怪了）

C二级辅导-温度转换（C语言代码）

C语言训练-自守数问题（C语言代码） long long

　　评论区

数组输出（C语言代码）--此题的题目描述有问题

字符串的输入输出处理（C语言代码）

【计算两点间的距离】（C语言代码）