C语言---最大公约数和最小公倍数的求法

简介: C语言---最大公约数和最小公倍数的求法
#include <stdio.h>
//欧几里得算法求的最大公约数
int gcd(int a, int b)
{
    //一定要确保a>b
    if (a < b)
    {
        int temp = a;
        a = b;
        b = temp;//作用是创建临时变量将a和b的数值置换
    }
    while (b != 0)//当b不等于0时,继续执行循环
    {
        int remainder = a % b;//计算余数
        //算完余数后,进行新的计算,届时a位置上面的值由b替代
        //也就是第二次计算时,b坐在第一次a的位置,
        // 第一次的余数坐在第一次计算时b的位置
        a = b;
        b = remainder;//此时b的位置是余数
    }
    //注意这个循环的条件b != 0
    //当下一次计算的时候,上一次计算时
    //算出的余数不为0,那么就在下一次计算的时候坐在b的位置
    //但要是上一次计算的余数为0,也就是下次计算的b=0,
    // 那么循环就停止了,
    //恰好上一次循环的b现在在a的位置,所以现在a位置上面的值就是
    //我们要求的最大公约数
    return a;
}
 
//根据最大公约数求得最小公倍数
//最小公倍数就是你输入的两个值相乘再除以最大公约数
int lcm(int a, int b, int gcdValue)
{
    return a * b / gcdValue;
}
//这种题最关键的就是求出最大公约数
// 再根据最大公约数求出最小公倍数
 
 
int main()
{
    int m, n;
    scanf("%d %d", &m, &n);
    //计算最大公约数
    int gcdValue = gcd(m, n);
    //计算最小公倍数
    int lcmValue = lcm(m, n, gcdValue);
    //打印最大公约数和最小公倍数之和
    printf("%d", gcdValue + lcmValue);
 
 
    return 0;
}
 
 
如果给的数据特别大,就在每个int前面添加long long
并且在占位符%d前面添加ll
目录
相关文章
|
2月前
|
算法 C语言
【C语言程序设计——函数】利用函数求解最大公约数和最小公倍数(头歌实践教学平台习题)【合集】
本文档介绍了如何编写两个子函数,分别求任意两个整数的最大公约数和最小公倍数。内容涵盖循环控制与跳转语句的使用、最大公约数的求法(包括辗转相除法和更相减损术),以及基于最大公约数求最小公倍数的方法。通过示例代码和测试说明,帮助读者理解和实现相关算法。最终提供了完整的通关代码及测试结果,确保编程任务的成功完成。
97 15
|
2月前
|
算法 C语言
【C语言程序设计——循环程序设计】求解最大公约数(头歌实践教学平台习题)【合集】
采用欧几里得算法(EuclideanAlgorithm)求解两个正整数的最大公约数。的最大公约数,然后检查最大公约数是否大于1。如果是,就返回1,表示。根据提示,在右侧编辑器Begin--End之间的区域内补充必要的代码。作为新的参数传递进去。这个递归过程会不断进行,直到。有除1以外的公约数;变为0,此时就找到了最大公约数。开始你的任务吧,祝你成功!是否为0,如果是,那么。就是最大公约数,直接返回。
103 18
|
2月前
|
存储 算法 安全
【C语言程序设计——选择结构程序设计】判断一个数是不是5和7的倍数(头歌实践教学平台习题)【合集】
本任务要求输入一个正整数,判断其是否同时是5和7的倍数,若是输出&quot;Yes&quot;,否则输出&quot;No&quot;。内容涵盖选择结构的基本概念、主要语句类型(if、if-else、switch)及条件判断逻辑,帮助理解编程中的分支执行与条件表达式。测试用例包括正数、负数及非倍数情况,确保代码逻辑严谨。通关代码示例如下: ```cpp #include &quot;stdio.h&quot; int main(){ int a; scanf(&quot;%d&quot;, &a); if (a &lt;= 0){ printf(&quo
67 0
|
9月前
|
存储 安全 C语言
【C语言刷题每日一题】——求最大公约数(带数学计算过程详解)
【C语言刷题每日一题】——求最大公约数(带数学计算过程详解)
|
9月前
|
C语言 Windows
C语言素数的不同求法
C|素数的不同求法及在线测试比较
|
9月前
|
算法 C语言
C语言——最大公因数和最小公倍数
C语言——最大公因数和最小公倍数
522 0
|
算法 C语言
C语言求最小公倍数和最大公约数三种算法(经典)
把以前写的一些经验总结汇个总,方便给未来的学弟学妹们做个参考!                                                                                                                       ...
1950 0
|
2月前
|
存储 算法 C语言
【C语言程序设计——函数】素数判定(头歌实践教学平台习题)【合集】
本内容介绍了编写一个判断素数的子函数的任务,涵盖循环控制与跳转语句、算术运算符(%)、以及素数的概念。任务要求在主函数中输入整数并输出是否为素数的信息。相关知识包括 `for` 和 `while` 循环、`break` 和 `continue` 语句、取余运算符 `%` 的使用及素数定义、分布规律和应用场景。编程要求根据提示补充代码,测试说明提供了输入输出示例,最后给出通关代码和测试结果。 任务核心:编写判断素数的子函数并在主函数中调用,涉及循环结构和条件判断。
80 23
|
14天前
|
人工智能 Java 程序员
一文彻底搞清楚C语言的函数
本文介绍C语言函数:函数是程序模块化的工具,由函数头和函数体组成,涵盖定义、调用、参数传递及声明等内容。值传递确保实参不受影响,函数声明增强代码可读性。君志所向,一往无前!
16 1
一文彻底搞清楚C语言的函数
|
2月前
|
C语言
【C语言程序设计——函数】亲密数判定(头歌实践教学平台习题)【合集】
本文介绍了通过编程实现打印3000以内的全部亲密数的任务。主要内容包括: 1. **任务描述**:实现函数打印3000以内的全部亲密数。 2. **相关知识**: - 循环控制和跳转语句(for、while循环,break、continue语句)的使用。 - 亲密数的概念及历史背景。 - 判断亲密数的方法:计算数A的因子和存于B,再计算B的因子和存于sum,最后比较sum与A是否相等。 3. **编程要求**:根据提示在指定区域内补充代码。 4. **测试说明**:平台对代码进行测试,预期输出如220和284是一组亲密数。 5. **通关代码**:提供了完整的C语言代码实现
68 24