最大公约数和最小公倍数
从键盘中输入a,b,求其最大公约数和最小公倍数
#include<stdio.h>
int main() {
int a, b, c, m, t;
printf("请输入两个整数:\n");
scanf_s("%d%d", &a, &b);
if (a < b) {
t = a;
a = b;
b = t;
}
m = a * b;
c = a % b;
while (c != 0) {
a = b;
b = c;
c = a % b;
}
printf("最大公约数是:\n%d\n", b);
printf("最小公倍数是:\n%d\n", m/b);
}
运行的代码如下:
求最大公约数的方法一般是辗转相除法(又称欧几里得算法、辗转相减法)。在C语言中,使用这种算法可以快速计算两个整数之间的最大公约数。
辗转相除法的原理是:对于两个正整数a和b,假设它们的最大公约数为c,则有以下定理:
-
如果a能够被b整除,则c=b;
-
如果a不能被b整除,则c等于b和a除以b的余数的最大公约数,即c=gcd(b,a%b)。
-
c=gcd(b,a%b)
-
这行代码的意思是求a和b的最大公约数,使用了递归的方式。具体解释如下:
- % 表示取模运算,即求a除以b的余数。
- a%b 表示a除以b的余数。
- gcd函数表示求最大公约数,其中参数a和b表示要求最大公约数的两个数。
- 当b为0时,a就是最大公约数,直接返回a。
- 当b不为0时,递归调用gcd函数,传入参数b和a%b,继续求b和a%b的最大公约数。
- 最终得到的c就是a和b的最大公约数。
CSDN-Ada助手: 非常棒的博客!你的解释非常清晰,我也学到了很多关于求任意次方后的最后三位数的方法。希望你能继续写下去,分享更多有趣的算法题目。另外,关于扩展知识和技能,我想提一下模运算。我们可以使用模运算来取一个数的最后几位数,这也是本题的解法之一。再次感谢你的分享! 如何写出更高质量的博客,请看该博主的分享:https://blog.csdn.net/lmy_520/article/details/128686434?utm_source=csdn_ai_ada_blog_reply2 如果您持续创作,完成第三篇博客,并且质量分达到 80 分以上,在评论区就有机会获得红包奖励哦!
CSDN-Ada助手: 恭喜您写了一篇关于最大公约数和最小公倍数的博客!这是一个非常有用的数学知识点,希望您能继续分享更多有关数学的知识。下一步的创作建议可以考虑介绍一些有趣的数学应用或者实际问题中的数学解决方法。期待您的下一篇博客! CSDN 会根据你创作的前四篇博客的质量,给予优秀的博主博客红包奖励。请关注 https://bbs.csdn.net/forums/csdnnews?typeId=116148&utm_source=csdn_ai_ada_blog_reply4 看奖励名单。
CSDN-Ada助手: 恭喜你又写了一篇非常实用的博客,介绍了冒泡排序在c/c++两种语言中的实现方法。你的文章非常详细,让我对冒泡排序有了更深入的了解。建议你在未来的创作中,可以考虑多介绍一些常用的排序算法或者其他经典的算法,让读者们更全面地学习和掌握计算机科学的知识。期待你的更多精彩文章! CSDN 正在通过评论红包奖励优秀博客,请看红包流:https://bbs.csdn.net/?type=4&header=0&utm_source=csdn_ai_ada_blog_reply3,我们会奖励持续创作和学习的博主,请看:https://bbs.csdn.net/forums/csdnnews?typeId=116148&utm_source=csdn_ai_ada_blog_reply3
CSDN-Ada助手: 推荐 算法 技能树:https://edu.csdn.net/skill/algorithm?utm_source=AI_act_algorithm
CSDN-Ada助手: 恭喜你这篇博客进入【CSDN每天最佳新人】榜单,全部的排名请看 https://bbs.csdn.net/topics/614568427。