前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >C语言求两数最大公约数和最小公倍数

C语言求两数最大公约数和最小公倍数

作者头像
编程小顺
发布2021-10-13 10:39:52
3.8K0
发布2021-10-13 10:39:52
举报
文章被收录于专栏:知识小木屋知识小木屋

辗转相除法又名欧几里德算法,是求最大公约数的一种方法。它的具体做法是:用较大数除以较小数,再用出现的余数(第一余数)去除除数,再用出现的余数(第二余数)去除第一余数,如此反复,直到最后余数是0为止。如果是求两个数的最大公约数,那么最后的除数就是这两个数的最大公约数。

———来源:搜狗百科

核心思路

求最大公约数方法:辗转相除法

求最小公约数方法:(num1 x num2)÷最大公约数

例:求125 15 两数的最大公约数和最小公倍数。

解:125 / 15 = 8 ······· 5

15 / 5 = 3 ······· 0

所以两数的最大公约数为5,最小公倍数为 (125 x 15) ÷ 5 = 375

C语言代码

代码语言:javascript
复制
#include <stdio.h>

int main() {
    int a, b, n1, n2, t; // 声明a b n1 n2 t
    printf("请输入两位数:\n");
    scanf("%d %d", &a, &b); // 用户输入a b
    n1 = a; // 赋值
    n2 = b; // 赋制
    //辗转相除开始
    while (n2) {
        t = n1 % n2;
        n1 = n2;
        n2 = t;
    }
    //辗转相除结束
    //输出结果
    printf("最大公约数 %d\n", n1);
    printf("最小公倍数是 %d\n", a * b / n1);
    return 0;
}

运行编译上述代码,输入125 15,将会得到以下结果:

代码语言:javascript
复制
请输入两位数:
125 15
最大公约数 5
最小公倍数是 375
本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2021-06-18,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 知识小木屋 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档