【C语言】两个整数最大公约数和最小公倍数

这篇具有很好参考价值的文章主要介绍了【C语言】两个整数最大公约数和最小公倍数。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目

输入两个整数,求这两个数的最大公约数和最小公倍数。

 我们先来讲最大公约数

第一种求法(辗转相除法)这个方法代码较洁简,我也比较推荐就是刚开始有点比较难了解。

首先,来看看怎么求最大公约数,求最大公约数需要用到欧几里得算法,也称为辗转相除法。算法就是用两数中较大的数a除以另一个数b得出余数c,然后判断c是否为0(意思a能够整除b),为0则b为最大公因数;反之,则把b作为a,c作为b,继续上面的操作,直至余数为0.

翻译一下,用个简单的代码输入输出解释一下:

输入18 24  (这里本来要比较两数的大小,然后直接公式得到,但也可以省去比大小,用循环)

第一次循环

a = 18    b = 24    c = a%b = 18%24 = 18 

然后将a=b    b=c    (结合第二次循环,可以得出我们不需要比大小,第一次小除大,会两值不会变,但位置反,可以直接用)

a = 24    b=18

第二次循环

a = 24    b = 18    c = a%b = 24%18 = 6 

然后将结果a = b    b =c

a =18     b=6    (可以静下心来感受一下这里面值相对大小的改变)

 第三次循环

a = 18    b = 6     c = a%b = 18%6 = 0

c的结果等于0时循环结束。

 代码如下

#include <stdio.h>

int main()
{
    int m = 0;
    int n = 0;
    int temp = 0;
    
    scanf("%d %d", &m, &n);//两个整数

    while (tmp = m % n)//循环,大小不对,自动换位置。
    {
        m = n;
        n = temp;
    }
    printf("最大公约数为:%d\n", n);
    return 0;
}

还有一个最直接的办法,将所有的情况都举出来。

思路:

两种情况讨论

1.如果大数可以整除小数,那么最大公约数为小数。

2.如果不能整除小数,那就找一个比较大,但时小于较小的数,能被两数同时整除的数。

代码如下: 

#include<stdio.h>
int main()

{
    int a = 0;
    int b = 0;
    printf("请输入两个整数:");
    scanf("%d%d", &a, &b);
    if (a >= b)

{
        int i = 0;
        for (i = b; i >= 1; i--)

        {
            if (a%i == 0 && b%i == 0)

                {
                printf("最大公约数为:%d\n", i);
                break;
                }
        }
}
    else

{
        int j = 0;
        for (j = a; j >= 1; j--)

        {
            if (a%j == 0 && b%j == 0)

                {
                printf("最大公约数为:%d\n", j);
                break;
                }
         }
 }
    return 0;
}

 求完最大公约数,接下来求最小公倍数

根据公式法,我们可以知道两数a和b的乘积等于它们的最大公约数和最小公倍数的积,所以最小公倍数可以通过最大公约数来求。

因为上面已经求完最大公约数,所以可以直接用两数相乘然后除最大公约数

代码如下

#include<stdio.h>
int main()
{
    int a, b, c, d;
    
    scanf("%d %d %d", &a, &b,%c);//a,b为数,c为最大公约数;
     
    d = a * b / c;
    
    printf("%d",c);
 } 

谢谢大家的观看! 文章来源地址https://www.toymoban.com/news/detail-440393.html

到了这里,关于【C语言】两个整数最大公约数和最小公倍数的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C语言—最大公约数和最小公倍数

    作者主页: paper jie的博客_CSDN博客-C语言,算法详解领域博主 本文作者: 大家好,我是paper jie,感谢你阅读本文,欢迎一建三连哦。 本文录入于 《算法详解》专栏,本专栏是针对于大学生,编程小白精心打造的。笔者用重金(时间和精力)打造,将算法基础知识一网打尽,希望

    2024年02月13日
    浏览(41)
  • 【C语言】求最大公约数和最小公倍数

    方法一:利用 定义法 求最大公因数和最小公倍数 方法二:最小公倍数求法同上, 最大公约数方法不同 方法一方法二的结果示例如下   方法三:利用 辗转相除法 求最大公约数和最小公倍数 法(1)结果示例如下:  法(2)示例结果如下:  以上就是用C语言循环和循环之前的

    2024年02月07日
    浏览(53)
  • 【c语言】—求最大公约数和最小公倍数多种方法

    目录 一.求最大公约数 1.枚举法求最大公约数 2.辗转相除法 二.求最小公倍数 1.枚举法求最小公倍数 2.简易法 3.公式法 思路:先求两个数中的最小值,最大公约数不可能大于两个数的最小数 比如6和18,最大公约数就是6 再如3和9,最大公约数就是3 然后再从1开始循环遍历到最小

    2024年02月08日
    浏览(59)
  • 【C语言】一篇博客带你弄懂最大公约数和最小公倍数

    我们在C语言的学习中,经常会遇到这样一些数学题目,良好掌握这些题目有利于我们理解和学习C语言,话不多说,直接进入主题 最大公约数: 首先我们举个例子,比如12 和16,12的约数有(1,2 ,3,4,6,12),16的约数有(1,2,4,8,16)公约数就是两个数共同的约数,(1,2,4)而公约数

    2024年02月04日
    浏览(48)
  • 最大公约数和最小公倍数问题

    等差数列 蓝桥杯192 gcd问题 题目描述 数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一 部分的数列,只记得其中 N 个整数。 现在给出这 N 个整数,小明想知道包含这 N 个整数的最短的等差数列有几项? 思路:求出每一项之差的最大公约数,以这个

    2023年04月09日
    浏览(41)
  • C++ 最大公约数与最小公倍数

    (一)简单的两个正整数  求 最大公约数 (引入专题) 思路: 根据 “欧几里得算法”  ,即 “辗转相除法” 原理如下: 题意: 求出   a  , b  两个正整数的最大公约数 设  k = a / b,   r = a % b 即    a = k * b + r 又设  d  为 a 和 b 的一个公约数 那么由  r = a - k * b,  可

    2024年02月06日
    浏览(45)
  • P1029 最大公约数和最小公倍数问题

    3 2 1 上题目链接: P1029 [NOIP2001 普及组] 最大公约数和最小公倍数问题 本小蒟蒻的原始思路就是枚举所有范围内的数,分别求出他们的最大公约数和最小公倍数,再看是否满足题意。 于是就有了以下一言难尽的东西(;′⌒`)↓ 皇天不负有心人,收到了2个TLE,其他全WA 自我反

    2024年02月19日
    浏览(40)
  • 【Python 随练】求最大公约数和最小公倍数

    输入两个正整数 m 和 n,求其最大公约数和最小公倍数。 在本篇博客中,我们将解决一个常见的数学问题:求两个正整数的最大公约数和最小公倍数。我们将提供问题的解析,并给出一个完整的代码示例来计算最大公约数和最小公倍数。 给定两个正整数m和n,我们需要求它们

    2024年02月09日
    浏览(72)
  • C++求最大公约数和最小公倍数的方法

    每次遇到最大公约数和最小公倍数时总是忘记,这里总结了两种求最大公约数和最小公倍数的方法。 欧几里得算法是求解两个数的最大公约数的一种常用方法。该算法基于以下原理:两个整数的最大公约数等于其中较小数和两数的余数之间的最大公约数。可以通过递归调用该

    2024年02月15日
    浏览(45)
  • 求其最大公约数和最小公倍数,一行代码完成

    题目:输入两个正整数 m 和 n,求其最大公约数和最小公倍数。 求出最大公约数就行,最小公倍数用m*n除以最大公约数就行

    2024年02月05日
    浏览(63)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包