C 练习实例16 – 最大公约数和最小公倍数

C 练习实例16 – 最大公约数和最小公倍数

C 语言经典100例

题目：输入两个正整数m和n，求其最大公约数和最小公倍数。

程序分析：

（1）最小公倍数=输入的两个数之积除于它们的最大公约数，关键是求出最大公约数；

（2）求最大公约数用辗转相除法（又名欧几里德算法）

1）证明：设c是a和b的最大公约数，记为c=gcd(a,b),a>=b,
令r=a mod b
设a=kc，b=jc，则k，j互素，否则c不是最大公约数
据上，r=a-mb=kc-mjc=(k-mj)c
可知r也是c的倍数，且k-mj与j互素，否则与前述k，j互素矛盾,
由此可知，b与r的最大公约数也是c，即gcd(a,b)=gcd(b,a mod b)，得证。

2）算法描述：

第一步：a ÷ b，令r为所得余数（0≤r

以上内容是否对您有帮助：
在文档使用的过程中是否遇到以下问题：

• 内容错误
• 更新不及时
• 链接错误
• 缺少代码/图片示列
• 太简单/步骤待完善
• 其他

更多建议：

提交建议
写笔记
我要补充

推荐文章

• C语言在线编译器：无需安装，轻松编写C语言程序
• 免费定制学习计划与服务推荐，开启你的编程狮之旅
• 编程狮年度盘点：2023年最受欢迎的编程课程和教程
• Gradle：现代化的构建自动化工具
• SQL分层查询：优化数据检索和分析的利器

推荐教程

• DLL入门
• C语言教程
• 程序员书单
• 腾讯代码安全指南
• 锐道展现中间件dorado9

推荐课程

• 全国计算机等级考试二级 C语言真题解析(二)
• 全国计算机等级考试二级 C语言真题解析(一)
• C语言快速入门70集_新手自学教程
• C语言入门课程
• C语言/C++零基础软件入门

精选笔记