求最小公倍数和最大公约数的流程图

【例题精讲】

（一）列举法：适用于数比较小的问题

例1 （1）求28和70的最大公约数；（2）求12和18的最小公倍数 解（1）28的约数有：1、2、4、7、14、28； 70的约数有；1、2、5、7、10、14、35、70。

因此，28与70的公约数有：1、2、7、14，其中最大的公约数为14，所以，（28，70）=14 （2）12的倍数有：12、24、36、48、60、72,…… 18 的倍数有36、72，…….，36是最小的公倍数 所以，[12，18]=36

（二）因式分解法：适用于数比较大的问题

现在以三个数为例来说明因式分解法求最大公约数和最小公倍数的求法，设自然数a，b，c的标准分解式为

a=pa1

 1 · pa2

 2·

。。。。。。。。。。。。。。。，，·，

pak

 k （p1<p2<…..<pk,αi≥0,i=1,2,„..,k）,

b= pβ1

 1 · pβ2

 2·

。。。。。。。。。。。。。。。。，

·pβk

 k （p1<p2<…..<pk, βi≥0,i=1,2,„..,k）,

c=pγ1

 1 · pγ2

 2·

。。。。。。。。。。。。。。。。，，

·pγk

 k （p1<p2<…..<pk, γi≥0,i=1,2,„..,k）,

则       （a，b，c）=pa1

1 ·pa2

 2·„·pak

 k , 其中αi=min{αi ，βi ，γi }（i=1，2，„,k）

博师堂国际教育 www.bostedu.com

好成绩，好未来！                                                 

[a,b,c]= pb1

 1 · pb2

 2·。。。。。。。。。。。。。。。。，，

·pbk

 k ,

其中bi=max{αi ，βi ，γi }（i=1，2，„,k）

说明：min{αi ，βi ，γi }表示在αi ，βi ，γi 这三个数中取最小的第一个，max{αi ，βi ，γi }表示在αi ，βi ，γi 这三个数中取最大的那一个，（其中i=1，2，„,n）

例2 求2520、14 850、819的最大公约数和最小公倍数。 解 先对这三个数分别分解质因数得； 2520=23

×32

×5×7=23

×32

×5×7×110

×130

 14850=2×33

×52

×11=2×33

×52

×70

×13 819=32

×7×13=23

×32

×50

×70

×11×13

所以：（2520，14850，819）=20

×32

×70

×110

×130

=9

[2520，14850，819]=23

×32

×50

×70

×110

×130

=5405400 （三）短除法：适用于数大小居中的情况

例3 求36，108，126的最大公约数和最小公倍数。 解：用短除法

用公约数2除„„„„„„„„„„2        36    108    126

 

用公约数3除„„„„„„„„„„„3      18     54     63

 

用公约数3除„„„„„„„„„„„„3     6     18     21

 

所得3个商数互质„„„„„„„„„„„    2      6      7

所以：（36，108，126）= 2×3×3 = 18

 

下面是求最小公倍数：

 

用公约数2除„„„„„„„„„„2        36    108    126

 

用公约数3除„„„„„„„„„„„3      18     54     63

 

用公约数3除„„„„„„„„„„„„3     6     18     21

 

用2与6两数公约数2除2和雀友6 „„„    2   2      6     7

                                     者饥      

所得3个商两两互质                         1      3     7

所以[36，108，126]=2×3×3×2×1×3×7=756

注意用短除法求若干个数的最大公约数与最小公倍数的区别。 *求n个数的最大公约数：

（1） 必须每次都用．．．．n个数的公约数去除

（2） 一直除到n个数的顷嫌槐商互质（但不一定两两互质） （3） n个数的最大公约数即位短处是中所有除数的乘积

*求n个数的最小公倍数： （1） 必须先用．．（如果有）n个数的公约数去除，除到n个数没有除去1以外的公约数后，再用．．n-1个数的公约数去除，除到n-1个

数没有除1以外的公约数后，再用n-2个数的公约数去除，如此继续下去，为保证这一条，每次所用的除数均可选质数。

（2） 只要有两个数（被除数）能被同一数整除，就要继续除，一定要除到n个数的商量两互质为止。 （3） n 个数的最小公倍数即为短除式中，所有除数和最后两两互质的商的乘积 （四）辗转相除法求最大公约数：理解比较难，使用很简单，尤其是数比较大

例4  从一张长2002毫米、宽847毫米的长方形纸片上剪裁下尽可能大的正方形，如果剩下的部分不是正方形，那么在剩下的纸片上

var script = document.createElement('script')script.src = 'http://static.pay.baidu.com/resource/baichuan/ns.js'document.body.appendChild(script)

博师堂国际教育 www.bostedu.com

好成绩，好未来！                                                 

在裁下一个边长尽可能大的正方形，按照上面的过程不断的重复，最后剪得的正方形的边长是多少毫米。

解   剪的过程如图17-1所示，其中第一、二次均剪下847×847平方毫米的正方形，第三、四次剪下边长308毫米的正方形，第五次剪下边长231毫米的正方形，第六、七、八次剪下边长77毫米的正方形。

 

1 2

3

4

5

6

7 8

                           图17-1

   以上的解题过程，实际上给出了求最大公约数的另一个办法—辗转相除法，这个过程的算式表示如下： 2002=847×2+308，847=308×2+231，308=231×1+77， 231= 77×3

由以上算式可以看出：这种方法就是用最大数除以小数，再用上次运算中的除数除以余数如此反复除，直至余数为零，最后一个除数就是两数的最大公约数。这是因为：两个数的最大公约数，同时是俩个数的约数，也就是余数的约数，拿这道题来说，2002和847的公约数，也就是847与308的公约数，也就是308与231的公约数，也就是231于77的公约数，由于231是77的公倍数，由于231是77的倍数，所以他们的最大公约数就是77，所以2002 与847 的最大公约数为77。

辗转相除法的竖式格式如下：      

        2 2002                  847  2               1694                  616             1 308                   231  3

      231                   231  

              77                     0

例5  用辗转相除法求1170、2574、3003的最大公约数。

分析   用辗转相除法求出其中任意两个数的最大公约数，再求出这个公约数与另一个数的最大公约数。 解  因为

                      5  1170            2574   2                           1170            2340                            0             234 

所以：（1170，2574）=234。

又因为                   1     234       3003      12                                195       2808                                 39        195      5                                           195                                            0 所以（234，3003）=39。因此（1170，2574，3003）=39。 （五）用最大公约数求最小公倍数

根据最大公约数与最小公倍数的乘积为这些数的乘积可知，要求两个数的最小公倍数，可先求出这两个数的最大公约数，再用最大公约数去除这两个数的乘积，就能得到他们的最小公倍数。 例如，因为（56，42）=14，所以[56，42]=56×42÷14=168。 （六）最大公约数与最小公倍数的其他应用。

下载文档到电脑，查找使用更方便

5下载券  169人已下载

下载

还剩2页未读，继续阅读

博师堂国际教育 www.bostedu.com

好成绩，好未来！                                                 

例6．现有4个自然数，他们的和是1111，如果要求这4个数的公约数尽可能大，那么，这4个数的公约数最大可能是多少？ 分析：由题中4个自然数，他们的和是1111，如果要求这4个数的公约数尽可能大，那么4个自然数的公约数也一定是1111的约数，这样，讨论4个数的最大公约数的问题可以转化为讨抡1111的约数问题。在此基础上来确定这4个数，使他们的和为1111且最大公约数为最大。

解：因为1111=101×11，其约数有1，11，101，1111。显然1111不符合要求，在考虑约数101，由于

 1111=101×11=101×（1+2+3+5）=101+101×2+101×3+101×5。

如果取101，101×2，101×3，101×5这4个数，就满足题目目的要求——其和为1111且他们的最大公约数为101。（由于11=1+2+3+5=1+1+3+6=„,所以满足条件的4个数并不唯一）。 例7 下面两个算式中，得数较大的是哪一个？

（1）

（1/24+1/29）×30；       （2）（1/31+1/37）×40

分析  如果算出得数，计算量很大，比较量很大。比较一下两个式子。括号内都是两个分子为1的分数相加，如果能使括号外部分相同，那么只需要括号内部分就可以了。

解：因为[30，40]=120，则(1/24＋1/29)×30=（1/24+1/29）÷4×4×30=（1/96+1/116）×120

             （1/31+1/37）×40=（1/31+1/37）÷3×3×40=（1/93+1/111）×120

由于1/93大于1/96，1/111大于1/116，所以（2）式得数较大。 注意：最大公约数与最小公倍数的性质，在解题中会经常遇到。

例8  如图所示，街道ABC在B处拐弯，在街道的一侧要等距离地安装路灯，要求在A,B,C G处各庄一盏路灯，问：这条街道最少要安

装多少盏路灯？

                A                    B

                             1625米                                                                             

                                              1170米   

                                             C

分析：由题中“等距离的安装路灯”可知，乡邻两盏路灯之间的距离必为1625（米）与1170（米）的公约数，又由“最少要安装多少盏路灯”可知，总的路灯数最少，则相 邻两盏路灯之间的距离要最大，于是问题转化为求1625于1170的最大公约数。 解：由于1625=25×65 ，1170=18×65，且（25，28）=1。 所以：（1625，1170）=65。从而，最少需要安装25+28+1=44(盏)。 答：最少需安装44盏路灯（相邻两盏灯之间的距离都是65米）

例 9已知两个自然数的差为2，他们的最小公倍数与最大公约数之差为142。求这两个自然数。

分析：设其中较小的一个自然数为x,另一个则为x+2,那么这两个自然数的最大公约数只有两种可能，一个为1，一个为2。若最大公约数为1，则他们的最小公倍数为142+1=143，又因为最大公约数乘以他们的最小公倍数恰为两个自然数的积，所以： 1×143=a×（a+2）=11×13

若最大公约数为2，则他们的最小公倍数为142+2=144，而：2×144=（a+2）×a=16×18。故本题有2个答案。  解   设其中一个自然数为x，另一个位x+2 （1）当（x, x+2）=1时，[x ,x+2]=142+=1=143, 而（x ,x+2）×[x ,x+2]= 1×143=11×13= x×（x+2） 所以x=11 ,x+2= 13

（2）当（x, x+2）=2时，[x ,x+2]=142+2=144, 而（x ,x+2）×[x ,x+2]= 2×144=16×18= x×（x+2） 所以x=16 ,x+2= 18

答：这两个自然数为11和13或16和18 。

 

例10．已知两个自然数的和是60，他们的最大公约数与最小公倍数之和是84，求这两个自然数个式多少？ 分析：不妨设这两个自然数为a ，b若（a ，b）=m .则a=mq1  b=mq2,且（q1  ， q2）=1 由题意可知a+b=60 ，即：a+b= mq1  + mq2 = m（q1  + q2）=60，

博师堂国际教育 www.bostedu.com

好成绩，好未来！                                                 

      a ×b=m×(mq1 q2) = m (a ，b) ×[a ，b] = m×[a ，b]

所以[a ，b]=（a ×b）/ m= mq1 q2又因为(a ，b)+ [a ，b]= m+ mq1 q2=84，故得知m为60和84的公约数。 而（60，84）=12，所以m只可取1、2、3、4、6、12六种可能值，但当m取1、2、3、4、6时均不能同时满足

m（q1  + q2）=60和m+ mq1 q2=84

所以m仅能取12 ，则q1  + q2=60÷12=5，

                   12+12q1 q2=12（1+ q1 q2）=84                       1+ q1 q2=7                          q1 q2=6

若q1 、q2 分别取2、3时，则相对应的a 、b值为24和36

解：设这两个自然数为a 、b令（a ，b）=m，有a=mq1  b=mq2（q1  ， q2为a ，b除以m所得的商）又因为[a ，b]= （a ×b）/ m = mq1  × mq2/ m = mq1 q2 

   而a+b= mq1  + mq2 = m（q1  + q2）=60

   (a ，b)+ [a ，b]= m+ mq1 q2=m（1+ q1 q2）=84，

所以m为60，84的约数，又因（60，84）=12，所以m只可取1、2、3、4、6、12六种可能。

   当m取1、2、3、4、6、12均不能使上述两式都成立，故m应取12

   由m（q1  + q2）=60，m = 12得q1  + q2 = 5，又由m（1+ q1 q2）=84，m = 12，1+ q1 q2=7，得q1 q2 = 6 所以q1  、 q2应分别取2、3，得a = 12×2 = 24，b = 12×3 = 36，故a、b可分别取24和36  答：这两个自然数为24和36 。

在掌握了最大公约数、最小公倍数的有关概念后，把这两个概念连在一起的公式：[a ，b] ×（a ，b）= a ×b

就显得非常重要，他非常明确的表达了这两个概念之间的关系，表明最大公约数与最小公倍数之间可以互相转化，这往往是解决有关整数问题的重要工具，例10就是一个典型的例子

用程序框图输出100以内能同时被3和5整除的数。这个程序框图如下图所示：

程序框图的优点：

1、采用简单规范的符号，画法简单；

2、结构清晰，逻辑性强；

3、便于描述，容易理解。

程序框图采用的符号：

1、箭头表示的是控制流；

2、矩形表示的是加工步骤；

3、菱形表示逻辑条件

扩展资料：

注意事项：

（1）绘制流程图时，为了提高流程图的逻辑性，应遵循从左到右、从上到下的顺序排列。

（2）绘制流程图时，为了提高流程图的逻辑性，应遵循从左到右、从上到下的顺序排列。一个流程从开始符开始，以结束符结束。开始符号只能出现一次，而结束符号可出现多次。若流程足够清晰，可省略开始、结束符号。

（3）菱形为判断符号，必须要有“是和否（或Y和N）”两种处理结果，意思是说，菱形判断框一定需要有两条箭头流出；且判断符号的上下端流入流出一般用“是（或Y）”，左右端流入流陪滚高出用“否（或Y）”。

（4）同一流程图内芦尺，符号大小需要保持一致，同时连接线不能交叉，连接线不能无故弯曲。

（5）流程处理关系为并行关系的，需要将流程放在同一高度。

（6）必要时应采用标注，以此来清晰地说明流程，标注要用专门的标注符号。

（7）处理流程须以单一入口和单一出口绘制，同一路径的指示箭头应只有一个。

（备橘9）同一路径的指示箭头应只有一个。

---