代码求最大公约数和最小公倍数

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

最大公约数：最大公因数，也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。Eg：求24和60的最大公约数，先分解质因数，得24=2×2×2×3，60=2×2×3×5，24与60的全部公有的质因数是2、2、3，它们的积是2×2×3=12，所以，（24、60）=12。（质因子分解法）

最小公倍数：两个或多个整数公有的倍数叫做它们的公倍数。

求最大公约数和最小公倍数

假设两个数a,b 他们的最大公约数为m 那么a,b的最小公倍数公式为：

因为：

a=m*i

b=m*j

最小公倍数为：m*i*j=(m*i)*(m*j)/m=a*b/m

a*b/m

所以求出a,b的最大公约数就可知其最小公倍数。

更相损减法：

《九章算術·方田》作分數約簡時，提到求最大公因數方法：反覆把兩數的較大者減去較小者，直至兩數相等，這數就是最大公因數。這方法除了把除法換作減法外，與輾轉相除法完全相同。例如書中求91和49的最大公因數：

91 > 49, 91 - 49 = 42

49 > 42, 49 - 42 = 7

42 > 7, 42 - 7 = 35

求最大公约数和最小公倍数的方法探析

求最大公约数和最小公倍数的方法多样，按照教材由基本到最优化的计算方法步步探讨，看看各自的利弊和特点。

例如求12和9的最大公约数和最小公倍数.通常有以下4种方法：

1、

它们的公约数 它们的公倍数

它们的最大公约数和最小公倍数分别是3和36

2、分解质因数法：

12=3×2 ×2 9=3×3

它们的最大公约数是3。最小公倍数是3×2×2×3=36

3、短除法：

4 3

它们的最大公约数是3

最小公倍数是3×4×3=36

4、特殊情况法

1）两数互质时：例如8和11 它们的最大公约是1最小公倍数是两数积88

2）一个数是另一个数的倍数时：例如3和12 它们的最大公约是较小数3最小公倍数是较大数12。

5、求最小公倍数的方法：大数翻倍法。例如：6和8 8的1倍、2倍......倍,其中最先同时是6的倍数的24即是它们的最小公倍数.

尽管在初学时我们是按照有繁到简、有难到易的这种逐步抽象顺序来学的，总结的短除法非常方便，而且相当多数同学，也常认为在使用了方法5、4或方法3时似乎就掌握了一

致远经典学堂：与经典同行，为成长导航 潘老师：15827559359 82337858

六年级数学奥林匹克专题讲座（潘） 分数的最大公约数和最小公倍数

知识要点：

1、求最大公约数时，先把带分数化为假分数，求得几个分数分子的最大公约数作为分子，分母的最小公倍数作分母，所得分数即为几个分数的最大公约数。

2、求几个分数的最小公倍数时，用这几个分数的分子的最小公倍数作分子，分母的最大公约数作分母，所得的分数为这几个数的最小公倍数。

典型例题：

例1、求下面各组的最大公约数。

（1）

35552， （2）5，2，6 46689

例2、求下列数的最小公倍数。 （1），

例3、有甲、乙、丙三种溶夜，分别为4

91215655526，和 （2），， 283556168189525132升，3升和2升。现要分别装入小瓶中，每649个小瓶装入液体的体积相同，并且无剩余。问最少要装多少瓶？每瓶装多少升？

例4、苹果每个重

35千克，梨每个重千克。那么最少需要多少个苹果，多少个梨，才2824能使苹

C语言求最大公约数和最小公倍数算法总结

单位：山东科技大学 作者：左键

摘 要：介绍自己通过学习使用C语言求任意两个数的最大公约数和最小公倍数的基本算法思想、算法过程、代码实现以及分析比较。

关键词：C语言 算法 最大公约数 最小公倍数 中图分类号： TP312 文献标识码：A

The algorithm summarization of evaluating the greatest common divisor and the least common multiple in C Language

Abstract：Introduction to the algorithm basic thought, algorithm process and code realization and its analysing comparison in terms of evaluating the greatest common divisor and the least common multiple of any two positive integers by learning to using

论在小学教材中求最大公约数和最小公倍数的方法

班级：08数三班 学号：30308346 姓名：钟世校

初等数论是研究整数最基本性质的一门十分重要的数学基础课程,整除理论是初等数论的基础,其中心内容是最大公约数理论和算术基本定理,而我现在要论述的是求最大公约数和最小公倍数的几种方法

首先,让我们一起在来来了解一下最大公约数与最小公倍数的定义:

最大公约数: 设a1 , a2 ,…，an (n≥2)是不全为零的整数,如果d| ai

(i =1,2,3…,n),则称d为 a1 , a2 ,…，an的公约数,全体公约数中最大的一个数称为 a1 , a2 ,…，an的最大公约数,记作(a1 , a2 ,…，an).

最小公倍数: 设a1 , a2 ,…，M (i an是非零整数.若有整数M, 使 ai|

an 的公倍数,公倍数中最小的正数,=1,2,3…,n ),则称 M为a1 , a2 ,…，

称为a1 , a2 ,…，an的最小公倍数,记作[a1 , a2 ,…，an]。 求最大公约数的方法通常有两种,即用分解质因数法求最大公约数或用辗转相除法求最大公约数（亦称

第十一节 最大公约数和最小公倍数应用题(二)

1．有12分米的铁丝8根，18分米的铁丝9根，24分米长的铁丝10根。现在要把这些铁线截成同样长的小段，不能浪费，这些铁丝最长能截成多少米一根？一共可以截多少根？

2．一根长方体木料长72厘米，比宽多12厘米，长是高的2倍，现要将这根木料锯成同样大小的正方体木块，木块的体积要最大，木料不能有剩余，可以锯成多少个正方体？

3．水果店里将168个苹果，120个梨，312个桔子分装在n个竹篮里去慰问残疾人。要求每篮中都有苹果、梨子、橘子，且每篮里的苹果数相同，梨子数相同，橘子数相同，n的最大值是多少？

4．长方形砖长42厘米，宽26厘米，用这种砖铺成一块正方形砖地，至少要几块砖？

尖子训练营 43 五年级数学

5．“六一”儿童节、幼儿园买了一些奶糖发给幼儿，如果只发给小班，每人可得15粒；只发给中班，每人可得12粒；只发给大班，每人可得10粒。如果将这些奶糖平均发给大、中、小班的每个幼儿，每

第十一节 最大公约数和最小公倍数应用题(二)

1．有12分米的铁丝8根，18分米的铁丝9根，24分米长的铁丝10根。现在要把这些铁线截成同样长的小段，不能浪费，这些铁丝最长能截成多少米一根？一共可以截多少根？

2．一根长方体木料长72厘米，比宽多12厘米，长是高的2倍，现要将这根木料锯成同样大小的正方体木块，木块的体积要最大，木料不能有剩余，可以锯成多少个正方体？

3．水果店里将168个苹果，120个梨，312个桔子分装在n个竹篮里去慰问残疾人。要求每篮中都有苹果、梨子、橘子，且每篮里的苹果数相同，梨子数相同，橘子数相同，n的最大值是多少？

4．长方形砖长42厘米，宽26厘米，用这种砖铺成一块正方形砖地，至少要几块砖？

尖子训练营 43 五年级数学

5．“六一”儿童节、幼儿园买了一些奶糖发给幼儿，如果只发给小班，每人可得15粒；只发给中班，每人可得12粒；只发给大班，每人可得10粒。如果将这些奶糖平均发给大、中、小班的每个幼儿，每

课程十一

最大公约数和最小公倍数

学习目标 1.倍数与约数的特性 2.倍与倍数的特性 3.分解质因数法 4.短除法 5.辗转相除法

重 点 1.几个数公有的约数，叫做这几个数的公约数；其中最大的一个，叫做 这几个数的最大公约数。 2.几个数公有的倍数，叫做这几个数的公倍数；其中最小的一个，叫做 这几个数的最小公倍数。

总 结 1.两个数的最大公约数的约数，都是这两个数的公约数。 2.两个数分别除以它们的最大公约数，所得的商一定是互质的。 3.两个自然数的最大公约数与最小公倍数的乘积等于这两个数的乘积。 4.两数互质，最大公约数是1，最小公倍数是两数之积。

5.两数成倍数关系，最大公约数是较小数，最小公倍数是较大数。

引 入

甲、乙、丙三个学生定期向某老师求教，甲每4天去一次，乙每6天 去一次，丙每9天去一次。如果这一次他们三人是3月23日都在这个老师 家见面，那么下一次三人都在这个老师家见面的时间是几月几日？ 基础知识 如果数a能被数b整除，a就叫做b的倍数，b就叫做a的约数。约数 和倍数都表示一个数与另一个数的关系，不能单独存在。如只能说16是某 数的倍数，2是某

一、教材分析

苏教版小学数学第十册中第22页—31页第三单元公倍和公因数数的教学，从教材分析，这章内容特别重要。准确迅速的找出它们的最大公因数与最小公倍数，是分数通分、约分必不可少的基础，而分数的通分、约分是进行分数加、减、乘、除四则运算的关键。对于求最大公因数与最小公倍数能否熟练掌握，直接决定了分数四则运算的准确率，因此求两个数的最大公因数与最小公倍数的学习之重要。而求两个数的最大公因数与最小公倍数的学习又牵涉到很多的概念。而且概念间内在联系紧密，可以说是环环相扣，有一个环节学习不好也都会直接影响到下后面的学习，所以最大公因数与最小公倍数的学习是小学生很难掌握的内容，又是至关重要的。它的概念多，环环相扣主要表现在：在学习最大公因数与最小公倍数时，学生要先掌握因数和倍数的概念，而要掌握因数与倍数的概念还要先掌握整除的概念，而整除这里又需要同学们能够掌握能被2、3、5整除的特征；除此之外，在求地大公因数与最小公倍数时，还讲到了两种特殊的关系，其中互质关系的两个数的最小公倍数是它们的乘积，最大公因数是1，而要正确是判断出两个数是不是互质关系，又要掌握质数与合数的概念；这里有需要同学们记住100以内的质数，这是有一定的难度的。只有这些都能够熟练地掌

五年级奥数－最大公约数与最小公倍数（１）

1．五年一班去划船，他们算了一下，如果增加一条船，正好每船坐6个，如果减少一条船，正好每船坐9人，这个班有多少人？

2．有一个电子表，每走9分钟这一次灯，每到整点响一次铃，中午12点整，电子表既响铃又灯，请问下一次既响铃又亮灯是几点钟？

3．两个整数的最小公倍数为140，最大公约数为4，且小数不能整除大数，求这两个数。

4．一个数被2除余1，被3除余2，被4除余3，被5除余4，被6除余5，此数最小是几？

5．一次会餐提供三种饮料，餐后统计，三种饮料共用65瓶，平均每2个人饮用一瓶A饮料，每3人饮用一瓶B饮料，每4人饮用一瓶C饮料，请问参加会餐的有多少人？

6．已知A与B的最大公约数为6，最小公倍数为84，且A×B＝42，求B。 7．两个数的最大公约数为12，最小公倍数为180，且较大数不能被较小数整除，求这两个数，

8．甲乙两数的最大公约数为75，最小公倍数为450，当这两个数分别为何值时，它们差最小。

9．已知A和B的最大公约数是31，且A×B＝5766，求A和B。

10．有一盘水果，3个3个地数余2个，4个4个数余3，5个5个数余4个，问这个盘子里最少有多少个水果？

11．有一个自然数，被6