Loading [MathJax]/jax/output/CommonHTML/config.js
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >求最大公约数和最小公倍数 -- C++ 辗转相除法

求最大公约数和最小公倍数 -- C++ 辗转相除法

作者头像
Skykguj
发布于 2022-09-09 03:52:02
发布于 2022-09-09 03:52:02
89100
代码可运行
举报
文章被收录于专栏:Skykguj 's BlogSkykguj 's Blog
运行总次数:0
代码可运行

问题引入

欧几里得算法又称辗转相除法,是用来求两个正整数最大公约数的算法。古希腊数学家欧几里得在其著作《The Elements》中最早描述了这种算法,所以被命名为欧几里得算法。

代码示例

C++ 辗转相除法:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
#include <iostream>
using namespace std;

int main()
{
    int r,m,n,min,max,product; //min代表最小公倍数,max代表最大公倍数;
    cout<<"请输入两个正整数:";
    cin>>m>>n;
    product = m * n;
    if(m < n) {int temp;temp = m;m = n;n = temp;}
    r = m % n;
    while(r != 0) //辗转相除法
    {
        m = n;
        n = r;
        r = m % n;
    }
    max = n;
    min = product / max;
    cout<<"最大公约数是:"<<max<<"\n"<<"最小公倍数是:"<<min;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2021 年 03 月,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

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

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

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
【C语言】求最小公倍数和最大公约数(辗转相除法)
利用格式输入语句将输入的两个数分别赋给 a 和 b,然后判断 a 和 b 的关系,如果 a 小于 b,则利用中间变量 t 将其互换。再利用辗转相除法求出最大公约数,进而求出最小公倍数。最后用格式输出语句将其输出。
全栈程序员站长
2022/08/30
2.6K0
【C语言】求最小公倍数和最大公约数(辗转相除法)
python计算最大公约数和最小公倍数_python怎么求最大公约数和最小公倍数
两个正整数a和b(a>b),它们的最大公约数等于a除以b的余数c和b之间的最大公约数。比如10和25,25除以10商2余5,那么10和25的最大公约数,等同于10和5的最大公约数。
全栈程序员站长
2022/08/29
6920
Python解决求最大公约数和最小公倍数问题
基本要求:1.程序风格良好(使用自定义注释模板),两种以上算法解决最大公约数问题,提供友好的输入输出。
全栈程序员站长
2022/08/29
1.3K0
Python解决求最大公约数和最小公倍数问题
最大公约数和最小公倍数
首先来回忆一下什么叫最大公约数:指两个或多个整数共有约数中最大的一个。比如60和24,60的约数有[1,2,3,4,5,6,10,12,15,20,30,60],24的约数有[1,2,3,4,6,8,12,24],他们共同的约数有[1,2,3,4,6,12],共同约数种最大的是12,所以最大公约数就是12。
贪挽懒月
2021/02/04
1.5K0
利用辗转相除法求最大公约数以及最小公倍数-Java
利用辗转相除法先求得 最大公约数,继而通过两数的乘积除以最大公约数,得到最小公倍数。
MickyInvQ
2020/09/27
1K0
C语言——求两个数的最大公约数和最小公倍数
设两数为a和b(a>b),用a除以b,得a÷b=q……r,若r=0 ,则最大公约数为b;若r≠0 ,则再用b÷r,得b÷r=q……r’,若r’=0,则最大公约数为r’,若r’≠0,则继续用r÷r’……直到能够整除为止,此时的除数即为最大公约数。
全栈程序员站长
2022/08/29
4840
求最大公约数(最大公因数)最小公倍数
求最大公约数(最大公因数) 1. 辗转相除法, 又名欧几里得算法(Euclidean algorithm):两个正整数a和b(a>b),它们的最大公约数等于a除以b的余数c和b之间的最大公约数。(比如10和25,25除以10商2余5,那么10和25的最大公约数,等同于10和5的最大公约数) ```java public static int gcd(int m,int n){ if (m%n==0){ return n; }
不吃紫菜
2022/08/18
6920
C语言题解——最小公倍数的三种求法(含最大公约数)
  最小公倍数是指能同时将两数整除的最小倍数,而最大公约数是则是能被两数同时整除的最小因数。最小公倍数有个特点,就是最小为两数中的较大值,最大为两数的乘积;最小公倍数则是最小为1,最大为两数中较小值(如果两数相同,那么最大公约数、最小公倍数是它们本身)🎉🎉🎉
北 海
2023/07/01
9260
C语言题解——最小公倍数的三种求法(含最大公约数)
三种算法求两个正整数的最大公约数和最小公倍数;求三个数的最大公约数和最小公倍数「建议收藏」
基本要求:1.程序风格良好(使用自定义注释模板),两种以上算法解决最大公约数问题,提供友好的输入输出。
全栈程序员站长
2022/08/29
2.9K0
三种算法求两个正整数的最大公约数和最小公倍数;求三个数的最大公约数和最小公倍数「建议收藏」
最大公约数和最小公倍数及其应用(Go语言解法)
image.png 最大公约数(greatest common divisor)欧几里得辗转相除法:gcd(x,y)表示x和y的最大公约数进入运算时:x!=0,y!=0,本质上就是不断转换成求等价更小数的最大公约数。如果x%y=0,返回y,即最大公约数。gcd(x,y)=gcd(y,x%y)证明:设k=x/y,b=x%y 则:x=ky+b如果n能够同时整除x和y,则(y%n)=0,(ky+b)%n=0,则b%n=0,即n也同时能够整除y和b。由上得出:同时能够整除y和(b=x%y)的数,也必然能够同时整除
李海彬
2018/03/19
3K0
最大公约数和最小公倍数及其应用(Go语言解法)
最大公约数和最小公倍数
       辗转相除法(欧几里得算法)算是求最大公约数最简单高效的算法了,这几行代码用最简洁的方式写了这个算法,值得牢牢记住:
刘开心_1266679
2019/02/14
7490
最大公约数与最小公倍数
又名欧几里德算法(Euclidean algorithm),它是已知最古老的算法, 其可追溯至公元前300年前。
pigeon
2022/04/11
3030
辗转相除法_欧几里得算法_java的实现(求最大公约数)
辗转相除法,又被称为欧几里德(Euclidean)算法, 是求最大公约数的算法。 当然也可以求最小公倍数。
谙忆
2021/01/21
1.1K0
详解最大公约数和最小公倍数
总体思路:假设要求a,b两个数的最大公约数,先求a,b两数的因子,因子会求吧(如果不会看这里,用for循环遍历从1到a的数,如果能被a整除,即取余为0,则这个数为a的因子。如果会请自动省略这里,蟹蟹٩('ω')و)然后同理求b的因子,找到相同的部分再从中找出最大值,不仅思路麻烦,时间复杂度还高,至于代码不贴了,诶,可不是因为我不会,是因为我懒啦。
一枕眠秋雨
2024/03/11
1360
808. 最大公约数 (递归gcd()函数)
原题链接 描述 输入两个整数 a 和 b,请你编写一个函数,int gcd(int a, int b), 计算并输出 a 和 b 的最大公约数。
浪漫主义狗
2022/07/11
4480
多种方法求解“最大公约数”和“最小公倍数”
采用枚举法求解两个数的最大公约数是我们最常使用到的方法,两个整数的最大公约数为a,则a应该是大于等于1,小于等于这两个数的最小数的。因此我们可以在该范围内对可能的数进行枚举即可。
灰小猿
2022/05/05
8840
【C语言】4种方法求最大公约数和最小公倍数及比较它们的运行时间
利用辗转相除法、穷举法、更相减损术、Stein算法求出两个数的最大公约数或者/和最小公倍数。
全栈程序员站长
2022/08/30
1.8K0
【C语言】4种方法求最大公约数和最小公倍数及比较它们的运行时间
萌新小白必做题(1):找两数间的最大公约数与最小公倍数
如果a>b,则a和b与a-b和b的最大公约数相同,即Gcd (a, b) = Gcd (a-b, b) 性质2 如果b>a,则a和b与a和b-a的最大公约数相同,即Gcd (a, b) = Gcd (a, b-a) 性质3 如果a=b,则a和b的最大公约数与a值和b值相同,即Gcd (a, b) = a = b
对编程一片赤诚的小吴
2024/01/23
1900
编程基础题模板:最大公约数和最小公倍数(辗转相除法)
自我介绍:一个脑子不好的大一学生,c语言接触还没到半年,若涉及到效率等问题,各位都可以在评论区提出见解,谢谢啦。
用户11039529
2024/03/25
1470
【C语言程序设计——函数】利用函数求解最大公约数和最小公倍数(头歌实践教学平台习题)【合集】
基本原理:for循环是一种常用的循环结构,它允许您指定一个初始化表达式、一个循环条件和一个更新表达式。语法格式为for(初始化表达式; 循环条件; 更新表达式)。初始化表达式在循环开始时执行一次,用于初始化循环变量。循环条件在每次循环迭代开始时进行检查,如果为真,则执行循环体中的代码。更新表达式在每次循环体执行完后执行,用于更新循环变量。
Rossy Yan
2025/01/13
2340
【C语言程序设计——函数】利用函数求解最大公约数和最小公倍数(头歌实践教学平台习题)【合集】
推荐阅读
相关推荐
【C语言】求最小公倍数和最大公约数(辗转相除法)
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档