前言：通过对【蓝桥杯】2020初赛的一道求既约分数的题目的讲解，引出关于求“最大公约数与最小公倍数”的方法汇总。对于“最大公约数与最小公倍数”来说，求解都有一些固定的方法，而这些方法一般都是固定的，只需要掌握方法，在日后遇到类似题目直接套用即可。目录蓝桥杯题目：既约分数 思路分析：完整代码：求最大公约数：一、辗转相除法二、更相减损法三、穷举法 四、递归（辗转相除） 求最小公倍数：一、穷举法二、a*b/最大公约数蓝桥杯题目：既约分数 思路分析：首先我们需要利用双层循环搭配产生分子与分母，得到这些数字后，在循环中判断这两个数是否满足他们的最大公约数为1即可，那么我们先做框架，再做细节，所以主函数（

本篇博客来讲一讲学习C语言过程中遇到的一种解法——辗转相除法首先我会介绍辗转相除法的概念，然后会用一道例题进行运用，最后会进行总结一、辗转相除法的概念辗转相除法又称欧几里得算法辗转相除法，是指用于计算两个非负整数a，b的最大公约数。应用领域有数学和计算机两个方面。由概念可知，该算法主要是用于两个非负整数的最大公约数，那么如何求呢，请看下文分析二、如何利用辗转相除法求两个数的最大公约数这里先看代码：intmain(){intm=0;intn=0;scanf("%d%d",&m,&n);intk=0;while(k=m%n){m=n;n=k;}printf("%d\n",n);return0;}所

题目描述求两个给定正整数的最大公约数和最小公倍数题目要求输入格式：输入在两行中分别输入正整数x和y输出格式：在一行中输出最大公约数和最小公倍数的值例如：输入1001520输出207600题目解析（1）几个整数中公有的约数，叫做这几个数的公约数；其中最大的一个，叫做这几个数的最大公约数例如：求24和60的最大公约数，先分解质因数，得24=2×2×2×3，60=2×2×3×5，24与60的全部公有的质因数是2、2、3，它们的积是2×2×3=12，所以，（24，60）=12。（2）几个自然数公有的倍数，叫做这几个数的公倍数，其中最小的一个自然数，叫做这几个数的最小公倍数例如：求6和15的最小公倍数。

题目描述求两个给定正整数的最大公约数和最小公倍数题目要求输入格式：输入在两行中分别输入正整数x和y输出格式：在一行中输出最大公约数和最小公倍数的值例如：输入1001520输出207600题目解析（1）几个整数中公有的约数，叫做这几个数的公约数；其中最大的一个，叫做这几个数的最大公约数例如：求24和60的最大公约数，先分解质因数，得24=2×2×2×3，60=2×2×3×5，24与60的全部公有的质因数是2、2、3，它们的积是2×2×3=12，所以，（24，60）=12。（2）几个自然数公有的倍数，叫做这几个数的公倍数，其中最小的一个自然数，叫做这几个数的最小公倍数例如：求6和15的最小公倍数。

题目：从键盘输入两个数，求这两个数的最大公约数。            =========================================================================            思路一：普通方法总体思路：（一）.生成相关变量；从键盘输入两个数；再使用三目操作符（条件操作符）找出较小值。        （二）.使用while循环，在循环中设置if条件判断语句，用两数分别 模以较小值，能整除（没有余数）则较小值就是最大公约数，不能整除（没有余数）则较小值自减1，直到能整除，此时较小值就是最大公约数，进行打印。             

求最大公约数是习题中比较常见的类型，下面小编会给大家提供五种比较常见的算法，记得帮忙点个赞哦！一般来说，最大公约数的求法大概有5种方法一：短除法    短除法是求最大公因数的一种方法，也可用来求最小公倍数。求几个数最大公因数的方法，开始时用观察比较的方法，即：先把每个数的因数找出来，然后再找出公因数，最后在公因数中找出最大公因数。后来，使用分解质因数法来分别分解两个数的因数，再进行运算。之后又演变为短除法。短除法运算方法是先用一个除数除以能被它除尽的一个质数，以此类推，除到两个数的商是互质数为止。    简单来说就是逐步找出两个数的所有公约数，再将这些公约数累乘起来，就能得到最大公约数啦！a=

求最大公约数是习题中比较常见的类型，下面小编会给大家提供五种比较常见的算法，记得帮忙点个赞哦！一般来说，最大公约数的求法大概有5种方法一：短除法    短除法是求最大公因数的一种方法，也可用来求最小公倍数。求几个数最大公因数的方法，开始时用观察比较的方法，即：先把每个数的因数找出来，然后再找出公因数，最后在公因数中找出最大公因数。后来，使用分解质因数法来分别分解两个数的因数，再进行运算。之后又演变为短除法。短除法运算方法是先用一个除数除以能被它除尽的一个质数，以此类推，除到两个数的商是互质数为止。    简单来说就是逐步找出两个数的所有公约数，再将这些公约数累乘起来，就能得到最大公约数啦！a=

基本介绍：最大公约数（greatestcommondivisor，简写为gcd；或highestcommonfactor，简写为hcf)，指某几个整数共有因子中最大的一个。最大公约数能够整除一个整数的整数称为其的约数（如5是10约数）；能够被一个整数整除的整数称为其的倍数（如10是5的倍数）；如果一个数既是数A的约数，又是数B的约数，称为A,B的公约数，A,B的公约数中最大的一个（可以包括AB自身）称为AB的最大公约数定义：如果有一个自然数a能被自然数b整除，则称a为b的倍数，b为a的约数。几个自然数公有的约数，叫做这几个自然数的公约数。公约数中最大的一个公约数，称为这几个自然数的最大公约数。

目录前言一、枚举法二、辗转相除法三、更相减损法前言如何求两个数的最大公约数是非常经典的问题，求解的方法也有很多，本文主要介绍其中的三种方法，分别是：枚举法、辗转相除法和更相减损法。 一、枚举法两个数的最大公约数一定小于或等于两数中较小的数，并且这两个数必定至少存在一个公因数1，利用这两个条件，可以将两个数的最大公约数的所有可能都列举出来。#includeintmain(){ inta=0; intb=0; intmin=0; scanf("%d%d",&a,&b); if(a>b) min=b; else min=a; for(inti=min;i>0;i--)//i：min->1 {

方法一：用函数实现求两个数的最大公约数和最小公倍数。使用的数学方法是欧几里得算法（辗转求余数法）defgcd(x,y):"""求最大公约数"""whiley%x!=0:x,y=y%x,xreturnxdeflcm(x,y):"""求最小公倍数"""returnx*y//gcd(x,y)print(gcd(9,6))#318print(lcm(6,9))#318方法二：非定义函数，但也是欧几里得算法（辗转求余数法）求最大公约数x=int(input('x='))y=int(input('y='))whiley%x!=0:x,y=y%x,xprint(x)#此处求出最大公约数方法三：循环求最大公约