Leyla

用户名：LeylaCaster

访问量：571

签　名：

是英雄就刷三百题

等　　级
排　　名	36014
经　　验	425
参赛次数	0
文章发表	1
年　　龄	0
在职情况	学生
学　　校	华科
专　　业

　　自我简介：

We are all in the gutter，but some of us are looking at the stars.

TA的其他文章

[编程入门]最大公约数与最小公倍数-题解(C语言代码)
浏览：368

你可能喜欢

C语言程序设计教程（第三版）课后习题6.9 （C++代码）论pow函数的应用

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

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

[编程入门]最大公约数与最小公倍数-题解(C语言代码)

　　作者: Leyla　　　　发表时间：2019-10-22 12:22:39 浏览：368　|　评论：0　

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

# C语言 最大公约数，最小公倍数

**最大公约数 Greatest Common Divisor(GCD)
最小公倍数 Least Common Multiple(LCM）**

## 递归+辗转相除法求最大公约数：

1. 如果a可以整除b，则b是最大公约数
2. 如果1不成立，最大公约数是b与a%b的最大公约数
###### 例如 求（319，377）：
######∵ 319÷377=0（余319）
######∴（319，377）=（377，319）；
######∵ 377÷319=1（余58）
######∴（377，319）=（319，58）；
######∵ 319÷58=5（余29）
######∴ （319，58）=（58，29）；
######∵ 58÷29=2（余0）
######∴ （58，29）= 29；
######∴ （319，377）=29。

- #### 子函数代码块

```c
//辗转相除法求最大公约数 
int gcd(int a,int b){
	if(a%b==0) return b;
	return gcd(b,a%b);
}
```

## 公式法求最小公倍数：
由于两个数的乘积等于这两个数的最大公约数与最小公倍数的积。即（a，b）×[a，b]=a×b。所以，求两个数的最小公倍数，就可以先求出它们的最大公约数，然后用上述公式求出它们的最小公倍数。

###### 例如，求[18，20]
######即得[18，20]=18×20÷（18，20）=18×20÷2=180
```c
//两个数的乘积等于这两个数的最大公约数与最小公倍数的积
int lcm(int a,int b){
	int res;
	res=a*b/gcd(a,b);
	return res;
} 
```
##总代码
```c
#include <stdio.h>
int gcd(int a,int b);
int lcm(int a,int b);
main(){
	int m,n ;
	scanf("%d %d",&m,&n);

printf("%d ",gcd(m,n));
	printf("%d",lcm(m,n));

return 0;
}

int gcd(int a,int b){
	if(a%b==0) return b;
	return gcd(b,a%b);
}

int lcm(int a,int b){
	int res;
	res=a*b/gcd(a,b);
	return res;
} 
```

0.0分

1 人评分

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

Leyla

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.9 （C++代码）论pow函数的应用

P1002 （C语言代码）

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

母牛的故事（C语言代码）

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

[编程入门]最大公约数与最小公倍数-题解(C语言代码)

评论区

精彩推荐

打水问题（C语言代码）

A+B for Input-Output Practice (II) （C语言代码）

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

哥德巴赫曾猜测（C语言代码）

【计算球体积】（C语言代码）

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

小九九（C语言描述,不看要求真坑爹）

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

整数平均值（C语言代码）

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

Leyla

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.9 （C++代码）论pow函数的应用

P1002 （C语言代码）

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

母牛的故事 （C语言代码）

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

[编程入门]最大公约数与最小公倍数-题解(C语言代码)

评论区

精彩推荐

打水问题 （C语言代码）

A+B for Input-Output Practice (II) （C语言代码）

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

哥德巴赫曾猜测 （C语言代码）

【计算球体积】 （C语言代码）

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

小九九 （C语言描述,不看要求真坑爹）

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

整数平均值 （C语言代码）

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

母牛的故事（C语言代码）

　　评论区

打水问题（C语言代码）

哥德巴赫曾猜测（C语言代码）

【计算球体积】（C语言代码）

小九九（C语言描述,不看要求真坑爹）

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

整数平均值（C语言代码）