搜档网
当前位置:搜档网 › 周四。最大公约数与最小公倍数

周四。最大公约数与最小公倍数

周四。最大公约数与最小公倍数
周四。最大公约数与最小公倍数

第五讲 最大公约数与最小公倍数

【知识导引】

一、约数的概念与最大公约数

约数又叫因数(在正整数范围内)整数a 能被整数b 整除,a 叫做b 的倍数,b 就叫做a 的约数。最大公约数:如果一个数既是数a 的约数,又是数b 的约数,称为[a,b]的约数。几个数公有的因数,叫做这几个数的公因数,其中最大的一个叫做这几个数的最大公因数。

1. 求最大公约数的方法

短除法:先找出所有共有的约数,然后相乘。例如:21812

39632

,所以(12,18)236=?=;

2. 最大公约数的性质

①几个数都除以它们的最大公约数,所得的几个商是互质数;

②几个数的公约数,都是这几个数的最大公约数的约数;

③几个数都乘以一个自然数n ,所得的积的最大公约数等于这几个数的最大公约数乘以n 。

二、倍数的概念与最小公倍数

对于整数m ,能被n 整除(n/m ),那么m 就是n 的倍数。如15能够被3或5整除,我们就说15是3的倍数,也是5的倍数。几个数公有的倍数叫做这几个数的公倍数,其中最小的一个叫做这几个数的最小公倍数。

1. 求最小公倍数的方法

短除法求最小公倍数 例如:21812

39632

,所以[]18,12233236=???=;

2. 最小公倍数的性质

①两个数的任意公倍数都是它们最小公倍数的倍数。

②两个互质的数的最小公倍数是这两个数的乘积。

③两个数具有倍数关系,则它们的最大公约数是其中较小的数,最小公倍数是较大的数。

练习

一.填空题

1. ab和都是自然数,如果ab?=10,ab和的最大公约数是(),最小公倍数是()。

2. 甲=2×3×5,乙=2×3×7,甲和乙的最大公约数是()×()=(),甲和乙的最小公倍数是()×()×()×()=()。

3. 所有自然数的公约数为()

4. 如果m和n是互质数,那么它们的最大公约数是(),最小公倍数是()。

二.求出下面每组数的最大公约数和最小公倍数(用短除法)。

1)45和60 最大公约数15,最小公倍数180。

2)36和60 最大公约数是12,最小公倍数180。

3)27和72 最大公约数是9,最小公倍数216。

4)76和80 最大公约数是4,最小公倍数1520。

最大公约数的三种算法 复杂度分析 时间计算

昆明理工大学信息工程与自动化学院学生实验报告 (2011 —2012 学年第 1 学期) 课程名称:算法设计与分析开课实验室:信自楼机房444 2011 年10月 12日 一、上机目的及内容 1.上机内容 求两个自然数m和n的最大公约数。 2.上机目的 (1)复习数据结构课程的相关知识,实现课程间的平滑过渡; (2)掌握并应用算法的数学分析和后验分析方法; (3)理解这样一个观点:不同的算法能够解决相同的问题,这些算法的解题思路不同,复杂程度不同,解题效率也不同。 二、实验原理及基本技术路线图(方框原理图或程序流程图) (1)至少设计出三个版本的求最大公约数算法; (2)对所设计的算法采用大O符号进行时间复杂性分析; (3)上机实现算法,并用计数法和计时法分别测算算法的运行时间; (4)通过分析对比,得出自己的结论。 三、所用仪器、材料(设备名称、型号、规格等或使用软件) 1台PC及VISUAL C++6.0软件 四、实验方法、步骤(或:程序代码或操作过程) 实验采用三种方法求最大公约数

1、连续整数检测法。 2、欧几里得算法 3、分解质因数算法 根据实现提示写代码并分析代码的时间复杂度: 方法一: int f1(int m,int n) { int t; if(m>n)t=n; else t=m; while(t) { if(m%t==0&&n%t==0)break; else t=t-1; } return t; } 根据代码考虑最坏情况他们的最大公约数是1,循环做了t-1次,最好情况是只做了1次,可以得出O(n)=n/2; 方法二:int f2(int m,int n) { int r; r=m%n; while(r!=0) { m=n; n=r; r=m%n; } return n; } 根据代码辗转相除得到欧几里得的O(n)= log n 方法三: int f3(int m,int n) { int i=2,j=0,h=0; int a[N],b[N],c[N]; while(i

C语言【最大公约数和最小公倍数】的两种方法

C语言【最大公约数和最小公倍数】的两种方法 By Minecig 1. //第一种是比较麻烦的方法,着重看加粗的函数实现部分:#include int main() { int yue(int m,int n); int bei(int m,int n); int gy,gb,i,j,l; printf("请输入两个整数:\n"); scanf("%d %d",&i,&j); if (i=1;i--) { if(m%i==0&&n%i==0) return i; } } int bei(int m,int n) { int i,t; if(m

return i; } } 2: //这种函数算法要好的多,利用了“辗转相除法”和“最小公倍数=x*y/最大公约数" 的算法#include int main() { int yue(int m,int n); int bei(int m,int n,int gy); int gy,gb,i,j,l; printf("请输入两个整数:\n"); scanf("%d %d",&i,&j); if (i

最大公约数的算法

. 1、查找约数法. 先分别找出每个数的所有约数,再从两个数的约数中找出公有的约数,其中最大的一个就是最大公约数. 例如,求12和30的最大公约数. 12的约数有:1、2、3、4、6、12; 30的约数有:1、2、3、5、6、10、15、30. 12和30的公约数有:1、2、3、6,其中6就是12和30的最大公约数. 2 更相减损术 《九章算术》是中国古代的数学专著,其中的“更相减损术”可以用来求两个数的最大公约数,即“可半者半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也。以等数约之。” 翻译成现代语言如下: 第一步:任意给定两个正整数;判断它们是否都是偶数。若是,则用2约简;若不是则执行第二步。 第二步:以较大的数减较小的数,接着把所得的差与较小的数比较,并以大数减小数。继续这个操作,直到所得的减数和差相等为止。 则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。 其中所说的“等数”,就是最大公约数。求“等数”的办法是“更相减损”法。 3、辗转相除法. 当两个数都较大时,采用辗转相除法比较方便.其方法是: 以小数除大数,如果能整除,那么小数就是所求的最大公约数.否则就用余数来除刚才的除数;再用这新除法的余数去除刚才的余数.依此类推,直到一个除法能够整除,这时作为除数的数就是所求的最大公约数. 例如:求4453和5767的最大公约数时,可作如下除法. 5767÷4453=1余1314 4453÷1314=3余511 1314÷511=2余292 511÷292=1余219 292÷219=1余73

219÷73=3 于是得知,5767和4453的最大公约数是73. 辗转相除法适用比较广,比短除法要好得多,它能保证求出任意两个数的最大公约数.4、求差判定法. 如果两个数相差不大,可以用大数减去小数,所得的差与小数的最大公约数就是原来两个数的最大公约数.例如:求78和60的最大公约数.78-60=18,18和60的最大公约数是6,所以78和60的最大公约数是6. 如果两个数相差较大,可以用大数减去小数的若干倍,一直减到差比小数小为止,差和小数的最大公约数就是原来两数的最大公约数.例如:求92和16的最大公约数.92-16=76,76-16=60,60-16=44,44-16=28,28-16=12,12和16的最大公约数是4,所以92和16的最大公约数就是4. 5、分解因式法. 先分别把两个数分解质因数,再找出它们全部公有的质因数,然后把这些公有质因数相乘,得到的积就是这两个数的最大公约数. 例如:求125和300的最大公约数.因为125=5×5×5,300=2×2×3×5×5,所以125和300的最大公约数是5×5=25. 6、短除法. 为了简便,将两个数的分解过程用同一个短除法来表示,那么最大公约数就是所有除数的乘积. 例如:求180和324的最大公约数. 因为: 5和9互质,所以180和324的最大公约数是4×9=36. 7、除法法. 当两个数中较小的数是质数时,可采用除法求解.即用较大的数除以较小的数,如果能够整除,则较小的数是这两个数的最大公约数. 例如:求19和152,13和273的最大公约数.因为152÷19=8,273÷13=21.(19和13都是质数.)所以19和152的最大公约数是19,13和273的最大公约数是13.

最大公约数和最小公倍数竞赛题

新课标七年级数学竞赛培训第32讲:最大公约数和最小公倍数 一、选择题(共10小题,每小题3分,满分30分) 2.(3分)古人用天干和地支记次序,其中天干有10个:甲,乙,丙,丁,戊,已,庚,辛,壬,癸,地支有12个:子,丑,寅,卯,辰,巳,午,未,申,酉,戌,亥,将天干的10个汉字和地支的12个汉字分别循环排列如下两列: 甲乙丙丁戊已庚辛壬癸甲乙丙丁戊已庚辛壬癸… 子丑寅卯辰巳午未申酉戌亥子丑寅卯辰巳午未申酉戌亥… 二、填空题(共5小题,每小题4分,满分20分) 11.(4分)a,b是彼此不相等的非零数字,则与4017的最大公约数是_________. 12.(4分)写出一组4个连续自然数,使它们从小到大顺次是5的倍数、7的倍数、9的倍数、11的倍数,这组自然数依次为1735,1736,1737,1738. 13.(4分)设m和n为大于0的整数,且3m+2n=225.

(1)如果m和n的最大公约数为15,则m+n=_________; (2)如果m和n的最小公倍数为45,则m+n=_________. 14.(4分)两个正整数之和为667,其最小公倍数是它们的最大公约数的120倍,那么满足条件的正整数有 _________组. 15.(4分)(a,b)表示两个正整数a和b的最小公倍数,例如[14,35]=70,则满足[x,y]=6,[y,z]=15的正整数组(x,y,z)共有_________组. 三、解答题(共8小题,满分100分) 16.(12分)甲地到乙地原来每隔45m要安装一根电线杆,加上两端的两根一共有53根电线杆.现在改成每隔60m 安装一根电线杆,除两端两根不需移动外,中途还有多少根不必移动? 17.(12分)如图,一个圆圈上有n (n<100=个孔.小明像玩跳棋一样,从A孔出发,逆时针方向将一枚棋子跳动,每步跨过若干个孔,希望跳一圈后回到A孔.他先每步跳过2个孔,结果只能跳到B孔;他又试着每步跳过4个孔,结果还是跳到B;最后他每步跳过6孔,正好回到A孔.问这个圆圈上一共有多少个孔? 18.(12分)23个不同的正整数的和是4845,问这23个数的最大公约数可能达到的最大值是多少写出你的结论,并说明你的理由. 19.(12分)张华、李亮、王民三位同学分别发出新年贺卡x、y、z张.如果已知x,y,z的最小公倍数为60,x 和y的最大公约数为4,y和z的最大公约数为3,那么张华发出的新年贺卡是多少张? 20.(12分)在一间屋子里有100盏电灯排成一横行,依从左到右的顺序编上号码1,2,3,…,100.每盏电灯上有一根拉线开关,最初所有电灯全是关的,现有100个学生在门外排着队,第一个学生走进屋来,把编号是1的倍数的电灯的开关拉一下;接着第二个学生走进屋来,把凡是编号是2的倍数的电灯开关拉了一下;…;最后第100个学生走进屋来,把编号是100的倍数的电灯的开关拉了一下,这样做过以后,问哪些电灯是亮的? 21.(12分)用整元的人民币购物,若用多于7元的任意元钱去买单价为3元和5元的两种雪糕,一定可以把钱花完,请证明这一结论. 22.(14分)已知两数和是60,它们的最大公约数与最小公倍数之和是84,求此二数. 23.(14分)甲、乙、丙三人到李老师那里求学,甲每6天去一次,乙每8天去一次,丙每9天去一次,如果8月17日他们三人在李老师处见面,那么下一次在李老师处见面的时间是几月几日呢?

最大公因数最小公倍数练习题

最大公因数最小公倍数练习题 班级( )姓名( ) ⒈ 写出下列每组数的最大公因数。 7和10( ) 13和26( ) 18和27( ) 4和9 ( ) 27和9 ( ) 12和18( ) 6和9 ( ) 10和6( ) 30和50( ) ⒉ 写出下列每个分数中分子和分母的最大公因数。 186( ) 4525( ) 3913( )369( )1917 ( ) 3、50以内最大质数与最小合数的乘积是( )。 4、从1、0、8、5四个数字中选三个数字,组成一个有因数5的最小三位数是( )。 5、一个三位数,能有因数2,又是5的倍数,百位上是最小的质数,十位上是10以内最大奇数,这个数是( )。 6、用10以下的不同质数,组成一个是3、5倍数的最大的三位数是( )。 7、有两个数都是质数,这两个数的和是8,两个数的积是15,这两个数是( )和( )。 8、有两个数都是质数,这两个数的和是15,两个数的积是26,这两个数是( )和( )。 9、 既不是质数,又不是偶数的最小自然数是( );既是质数,又是偶数的数是( );既是奇数又是质数的最小数是( );既是偶数,又是合数的最小数是( );既不是质数,又不是合数的是( );既是奇数,又是合数的最小的数是( )。 10、个位上是( )的数,既是2的倍数,也是5的倍数。 11、⊙47⊙同时是2、3、5的倍数,这个四位数最小是( ),这个四位数最大是( )。 12、两个质数的和是22,积是85,这两个质数是( )和( )。 113、一个四位数,千位上是最小的质数,百位上是最小的合数,十位上既不是质数也不是合数,个位上既是奇数又是合数,这个数是( )。 14、一个三位数,它的个位上是最小的质数,十位上是最小的合数,百位上的最小的奇数,这个三位数是( ),它同时是质数 ( )和( )的倍数. 15、如果两个不同的质数相加还得到质数,其中一个质数必定是( ). 16、在括号里填上适当的质数。 8=( )+( ) 12=( )+( )+( ) 15=( )+( ) 18=( )+( )+( ) 24=( )+( )=( )+( )=( )+( ) 17、我校微机室长120分米,宽90分米。现在要为微机室铺设地板砖。⑴从不浪费材料的角度考虑(使用的地板砖都是整块),可以选择边长是多少分米的正方形地板砖?⑵你认为选择边长是多少的方砖最大? 18、有一批墙面砖,每块砖的长是30厘米,宽25厘米。至少用多少块这样的砖才能铺成一个正方形?

matlab最大公约数 三种算法

算法设计与分析 11信本余启盛 118632011004 一、上机目的及内容 1.上机内容 求两个自然数m和n的最大公约数。 2.上机目的 (1)复习数据结构课程的相关知识,实现课程间的平滑过渡; (2)掌握并应用算法的数学分析和后验分析方法; (3)理解这样一个观点:不同的算法能够解决相同的问题,这些算法的解题思路不同,复杂程度不同,解题效率也不同。 二、实验原理及基本技术路线图 (1)至少设计出三个版本的求最大公约数算法; (2)对所设计的算法采用大O符号进行时间复杂性分析; (3)上机实现算法,并用计数法和计时法分别测算算法的运行时间; (4)通过分析对比,得出自己的结论。 三、所用仪器、材料(设备名称、型号、规格等或使用软件) 1台PC及VISUAL C++6.0软件matlab .2008 四、实验方法、步骤(或:程序代码或操作过程) 实验采用三种方法求最大公约数 1、连续整数检测法。 2、欧几里得算法 3、蛮力法(短除法) 根据实现提示写代码并分析代码的时间复杂度: 算法一:连续整数检测法。 CommFactor1 输入:两个自然数m和n 输出:m和n的最大公约数 1.判断m和n哪个数小,t=min(m,n) 2.如果m%t==0&&n%t==0 ,结束 2.1 如果t不是m和n的公因子,则t=t-1; 3. 输出t ;

根据代码考虑最坏情况他们的最大公约数是1,循环做了t-1次,最好情况是只做了1次,可以得出O(n)=n/2; 算法二:欧几里德算法 CommFactor2 输入:两个自然数m和n 输出:m和n的最大公约数 1. r = m % n; 2. 循环直到r 等于0 2.1 m = n; 2.2 n = r; 2.3 r = m % n; 3. 输出n ; 根据代码辗转相除得到欧几里得的: O(n)= log n 算法三:蛮力法(短除法) CommFactor3 输入:两个自然数m和n 输出:m和n的最大公约数 1.factor=1; 2.循环变量i从2-min(m,n),执行下述操作: 2.1 如果i是m和n的公因子,则执行下述操作: 2.1.1 factor=factor*i; 2.1.2 m = m / i; n = n / i; 2.2 如果i不是m和n的公因子,则i=i+1; 3. 输出factor; 根据代码考虑最坏情况他们的最大公约数,循环做了i-1次;最好情况是只做了1次,可以得出: O(n)=n/2; MATLAB程序代码: main.m x=fix(rand(1,1000)*1000); y=fix(rand(1,1000)*1000); for i=1:1000 A(i)=CommFactor2(x(i),y(i)); end x=x'; y=y';

小学数学解题方法解题技巧之最大公约数法

第一章小学数学解题方法解题技巧之最大公约数法 通过计算出几个数的最大公约数来解题的方法,叫做最大公约数法。 例1 甲班有42名学生,乙班有48名学生,现在要把这两个班的学生平均分成若干个小组,并且使每个小组都是同一个班的学生。每个小组最多有多少名学生?(适于六年级程度) 解:要使每个小组都是同一个班的学生,并且要使每个小组的人数尽可能多,就要求出42和48的最大公约数: 2×3=6 42和48的最大公约数是6。 答:每个小组最多能有6名学生。 例2 有一张长150厘米、宽60厘米的长方形纸板,要把它分割成若干个面积最大,井已面积相等的正方形。能分割成多少个正方形?(适于六年级程度) 解:因为分割成的正方形的面积最大,并且面积相等,所以正方形的边长应是1 50和60的最大公约数。 求出150和60的最大公约数: 2×3×5=30 150和60的最大公约数是30,即正方形的边长是30厘米。

看上面的短除式中,150、60除以2之后,再除以3、5,最后的商是5和2。这说明,当正方形的边长是30厘米时,长方形的长150厘米中含有5个30厘米,宽6 0厘米中含有2个30厘米。 所以,这个长方形能分割成正方形: 5×2=10(个) 答:能分割成10个正方形。 例3 有一个长方体的方木,长是3.25米,宽是1.75米,厚是0.75米。如果将这块方木截成体积相等的小正方体木块,并使每个小正方体木块尽可能大。小木块的棱长是多少?可以截成多少块这样的小木块?(适于六年级程度) 解:3.25米=325厘米,1.75米=175厘米,0.75米=75厘米,此题实际是求325、175和75的最大公约数。 5×5=25 325、175和75的最大公约数是25,即小正方体木块的棱长是25厘米。 因为75、175、325除以5得商15、35、65,15、35、65再除以5,最后的商是3、7、13,而小正方体木块的棱长是25厘米,所以,在75厘米中包含3个25厘米,在175厘米中包含7个25厘米,在325厘米中包含13个25厘米。 可以截成棱长是25厘米的小木块: 3×7×13=273(块) 答:小正方体木块的棱长是25厘米,可以截成这样大的正方体273块。 例4 有三根绳子,第一根长45米,第二根长60米,第三根长75米。现在要把三根长绳截成长度相等的小段。每段最长是多少米?一共可以截成多少段?(适于六年级程度)

最大公约数与最小公倍数练习题

最大公约数和最小公倍数练习题 一. 填空题。 3. 所有自然数的公约数为()。 4. 如果m和n是互质数,那么它们的最大公约数是(),最小公倍数是()。 5. 在4、9、10和16这四个数中,()和()是互质数,()和()是互质数,()和()是互质数。 6. 用一个数去除15和30,正好都能整除,这个数最大是()。 7. 两个连续自然数的和是21,这两个数的最大公约数是(),最小公倍数是()。 8. 两个相邻奇数的和是16,它们的最大公约数是(),最小公倍数是()。 9. 某数除以3、5、7时都余1,这个数最小是()。 10. 根据下面的要求写出互质的两个数。 (1)两个质数()和()。 (2)连续两个自然数()和()。 (3)1和任何自然数()和()。 (4)两个合数()和()。 (5)奇数和奇数()和()。 (6)奇数和偶数()和()。 二. 判断题。 1. 互质的两个数必定都是质数。() 2. 两个不同的奇数一定是互质数。() 3. 最小的质数是所有偶数的最大公约数。() 4. 有公约数1的两个数,一定是互质数。() 三. 直接说出每组数的最大公约数和最小公倍数。 26和13()13和6()4和6() 5和9()29和87()30和15() 13、26和52 ()2、3和7() 四. 求下面每组数的最大公约数和最小公倍数。(三个数的只求最小公倍数) 45和60 36和60 27和72 76和80 42、105和56 24、36和48 五. 动脑筋,想一想: 学校买来40支圆珠笔和50本练习本,平均奖给四年级三好学生,结果圆珠笔多4支,练习本多2本,四年级有多少名三好学生,他们各得到什么奖品?

最大公因数和最小公倍数总结(精)

最大公因数与最小公倍数 质数和合数 质数:一个数除了1和它本身以外,不再有别的因数,这个数叫质数。 因数:一个数除了1和它本身以外,还有别的因数,这个数叫做合数。 ☆1既不是质数也不是合数。 ☆最小的质数是2,最小的合数是4。 ☆常用的100以内的质数:2、3、5、7、11、13、17、19、23、29、31、37、 41、43、47、53、59、61、67、71、73、79、83、89、97共计25个。 ☆除了2,其余的质数都是奇数,除了2和5,其余质数的各位数字只能是1、3、7或9. 质因数:每个合数都可以写成几个质数相乘的形式,这几个质数就叫做这个合数的质因数。例如,因为70=2×5×7,所以2,5,7是70的质因数。 分解质因数:把一个合数用质因数相乘的形式表示出来,叫做分解质因数。 分解质因数的方法——短除法 把一个合数分解质因数,先用一个能整除这个合数的质数(通常从最小开始)去除,出得商如果是质数,就把除数和商写成相乘的形式;得出的商是合数,按照上面的方法继续除下去,直到得出的商是质数为止.然后把各个除数和最后的商写成连乘的形式。 ★合数都能分解质因数。 ★1是任何合数的因数。 ★质因数、合数与1组成自然数。 最大公因数 定义:几个自然数公有的因数,叫做这几个自然数的公因数。公因数中最大的一个公因数,称为这几个自然数的最大公因数。 最大公因数的求法: 1、短除法。 2、分解质因数法。 3、列举法。 例如:12=2×2×3 18=2×3×3 (12,18)=2×3=6 互质数:公因数只有1的两个数叫互质数。 互质的两个数不一定都是质数。有可能有以下几种情况: ⊙两个数都是质数。 ⊙两个数都是合数。 ⊙一个是质数,另一个是合数。 ⊙一个是1,另一个是质数或合数。 ⊙相邻的两个数都是互质的。 最小公倍数:几个数公有的倍数叫做这几个数的公倍数,其中最小的一个公倍数,叫做这几个数的最小公倍数。 最小公倍数的求法: 1、分解质因数法:如求两个数的最小公倍数,可以先分解质因数,找出两

最大公约数和最小公倍数的比较_教案教学设计

最大公约数和最小公倍数的比较 教学目标 (一)进一步理解并掌握最大公约数和最小公倍数的概念,分清求最大公约数和最小公倍数的相同点和不同点。 (二)培养学生仔细、认真的做题习惯和比较的思维方法。 (三)培养学生观察、分析、比较的能力。 教学重点和难点 最大公约数和最小公倍数异同点的比较。 教学用具 教具:小黑板,投影片。 学具:判断卡,选择卡。 教学过程设计 (一)复习准备 教师: ①什么叫最大公约数和最小公倍数? ②怎样求最大公约数和最小公倍数? ③求下面各题的最大公约数和最小公倍数?(口答) 8和1613和262和97和15 教师:对上面几道题你是怎么想的?各有什么特点?你能发现什么规律? 明确:

①两个数有倍数关系,最大公约数最较小数,最小公倍数是较大数。 ②两个数互质,最大公约数是1,最小公倍数是两个数乘积。 (二)学习新课 1.出示例5。 求28和42的最大公约数和最小公倍数。(要求学生独立完成。) 学生口述教师板书。 28和42的最大公约数是: 2×7=14 28和42的最小公倍数是 2×7×2×3=84 教师:观察上面两道题,谁能说出求最大公约数和求最小公倍数有什么地方相同?什么地方不同?(讨论) 在讨论的基础上,总结出下面的结论。 教师:为什么求最大公约数只要把所有除数乘起来,而求最小公倍数就要把所有除数和商都乘起来呢? 明确:求最大公约数是两个数公有质因数的积;求最小公倍数既要包含两个数公有质因数,又要包括各自独有的质因数。 教师:既然求两个数的最大公约数和最小公倍数的短除过程是相同的,那么,我们就可以用一个短除式来表示。例5怎样做简便?(由学生

最大公因数与最小公倍数的关系

最大公因数与最小公倍数的关系 日期(Class) __ 姓名(Name) _ 学号(Number) _ 得分_____ 我们上节课学习了最大公因数与最小公倍数,下面我们来做两道题来回顾一下。 [12,15] =60;(12,15)=3 [20,35] =140;(20,35)=5 好,大家都做出来了,说明大家掌握的都很好。 下面我们来探讨一下最大公因数与最小公倍数的关系。 首先,我们已经知道了[12,15] =60;(12,15)=3,现在大家算一算,12×15=180, 60×3=180,它们两个的结果相等,都是180,会不会是一种巧合呢,我们再来看另外两个数,随便说两个数,24和40,[24,40]=120,(24,40)=4,120×4=480,24×40=480,也是相等的。好,大家可以再随便几组数字,我们会发现一个关系,老师想考考大家的归纳总结能力,那谁能告诉我它们之间的关系。 对了,同学们说得都非常好,它们的关系就是: 两个数的乘积等于它们的最大公因数与最小公倍数的乘积。 大家要理解的记忆,不要死记硬背,要知道这个关系式怎么得来的。我们可以设这两个数为A,B,这样,我们就可以得到一个关系式: A×B=[A,B] ×(A,B) 例:两个数的最大公因数为10,最小公倍数为400,其中一个数为50,求另一个数? 10×400=4000 4000÷50=80 答:另一个数为80。 大家回去的时候,要理解并会把它们运用到应用题及现实生活中。我们再来总结一下今天所讲的内容,最大公因数与最小公倍数的关系,就是: 两个数的乘积等于它们的最大公因数与最小公倍数的乘积。 A×B=[A, B] ×(A, B)

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

最大公约数和最小公倍数怎么求? 首先把两个数的质因数写出来,最小公倍数等于它们所有的质因数的乘积(如果有几个质因数相同,则比较两数中哪个数有该质因数的个数较多,乘较多的次数)。 比如:求45和30的最小公倍数。 45=3*3*5 30=2*3*5 不同的质因数是2,3,5。3是他们两者都有的质因数,由于45有两个3,30只有一个3,所以计算最小公倍数的时候乘两个3. 最小公倍数等于2*3*3*5=90 又如:计算36和270的最小公倍数。 36=2*2*3*3 270=2*3*3*3*5 不同的质因数是5。2这个质因数在36中比较多,为两个,所以乘两次;3这个质因数在270个比较多,为三个,所以乘三次。 最小公倍数等于2*2*3*3*3*5=540 最大公约数和最小公倍数<练习题> 1.有一级茶叶96克,二级茶叶156克,三级茶叶240克,价值相等.现将这三种茶叶分别等分装袋(均为整数克),每袋价值相等,要使每袋价值最低应如何装袋? 2.a、b两数的最大公约数是12,已知a有8个约数,b有9个约数,求a与b. 3.两个数的积是6912,最大公约数是24,求:(1)它们的最小公倍数;(2)满足已知条件的自然数是哪几组? 4.甲、乙、丙三个学生定期向某老师求教,甲每4天去一次,乙每6天去一次,丙每9天去一次,如果这一次他们三人是3月23日都在这个老师家见面,那么下一次三人都在这个老师家见面的时间是几月几日? 5.求被5除余2,被6除余3,被7除4的大于1000、小于1500的所有自然数. 6.某个数与36的最大公约数是12,与36的最小公倍数是180,求这个数. 7.有三个自然数a、b、c,a与b的最大公约数是2;b和c的最大公约数是4;a和c的最大公约数是6;a、b、c三个数的最小公倍数是60,求这三个数的最小的和是多少? 答案仅供参考: 1.三种数量不等的茶叶价值相等,等分装袋后,每袋价值仍相等,由于每种茶叶的总价值相等,每袋价值也要相等,所以这三种茶叶分装的袋数也一定相同.为了使每袋价值最低,就应使袋数尽可能多,

(完整版)求最大公因数、最小公倍数练习题

一、基本概念: 公因数:两个或多个数都有的因数叫做公因数 公倍数:两个或多个数都有的倍数叫做公倍数 最大公因数:两个或多个数都有的因数里最大的叫做最大公因数 最小公倍数:两个或多个数都有的倍数里最小的叫做最小公倍数(没有最大公倍数) 公约数和最大公约数 几个数公有的约数,叫做这几个数的公约数;其中最大的一个,叫做这几个数的最大公约数. 例如:12的约数有1,2,3,4,6,12;30的约数有1,2,3,5,6,10,15,30。12和30的公约数有1,2,3,6,其中6是12和30的最大公约数。 一般地我们用(a,b)表示a,b这两个自然数的最大公约数,如(12,30)=6。如果(a,b)=1,则a,b两个数是互质数。 2、公倍数和最小公倍数 几个数公有的倍数,叫做这几个数的公倍数;其中最小的一个,叫做这几个数的最小公倍数。 例如:12的倍数有12,24,36,48,60,72,… 18的倍数有18,36,72,90,… 12和18的公倍数有:36,72…其中36是12和 18的最小公倍数。 一般地,我们用[a,b]表示自然数,a,b的最小公倍数,如[12,18]=36。 求最大公因数、最小公倍数习题 一、用短除法求几个数的最大公因数 12和30 24和3639和78 72和84 36和60 45和60 45和75 45和60 42、105和56 24、36和48 二、用短除法求几个数的最小公倍数。 25和30 24和3039和78 60和84 18和20 126和60 45和75 12和24 12和14 45和60 76和80 36和60 27和72 42、105和56 24、36和48

Java算法最大公约数和最小公倍数

Java算法最大公约数和最小公倍数 题目:输入两个正整数m和n,求其最大公约数和最小公倍数。 1.程序分析:利用辗除法。 最大公约数: public class CommonDivisor{ public static void main(String args[]) { commonDivisor(24,32); } static int commonDivisor(int M, int N) { if(N<0||M<0) { System.out.println("ERROR!"); return -1; } if(N==0) { System.out.println("the biggest common divisor is :"+M); return M; } return commonDivisor(N,M%N); } } 最小公倍数和最大公约数: import java.util.Scanner; public class CandC { //下面的方法是求出最大公约数 public static int gcd(int m, int n) {

while (true) { if ((m = m % n) == 0) return n; if ((n = n % m) == 0) return m; } } public static void main(String args[]) throws Exception { //取得输入值 //Scanner chin = new Scanner(System.in); //int a = chin.nextInt(), b = chin.nextInt(); int a=23; int b=32; int c = gcd(a, b); System.out.println("最小公倍数:" + a * b / c + "\n最大公约数:" + c); } }

最大公因数和最小公倍数练习题(专项练习)

最大公因数和最小公倍数练习题姓名:成绩 一. 填空题。 1. A与B的最小公倍数是10,那么它们的下一个公倍数应该是()。 2、所有自然数的公因数为()。 3、都是自然数,如果,的最大公因数是(),最小公倍数是()。 4. 如果m和n是互质数,那么它们的最大公因数是(),最小公倍数是()。 5. 在4、9、10和16这四个数中,()和()是互质数,()和()是互质数,()和()是互质数。 6. 分母是15的最简真分数一共有( )个。 三. 在左边写出每组数的最大公约数,右边写最小公倍数。 ()26和13()()13和6()()4和6() ()5和9()()29和87()()30和15()()13、26和52()()2、3和7() 四. 用短除法求下面每组数的最大公因数和最小公倍数。(注意格式完整) 45和60 36和60 27和72 72和80 五、生活中的应用(注意分清楚是与最大公因数有关还是与最小公倍数有关) 1、五年级(1)同学参加植树活动,如果8人一组或14人一组,正好分配完,五年级最少有多少人? 2、五年级某班学生在40—50人间,如果分成2人一组、5人一组、4人一组都恰好分完,

这个班有多少人? 3、两条钢条,一根长18米,一根长24米,要把它们截成同样长的小段,每段最长可以有几米?一共截成多少段? 4、7路车每5分钟发一班车,12路车每8分钟发,这两路车同时出发后,至少再经过多少分钟后又同时发车? 5、有饼干27千克、糖18千克,这些物品都刚好能平均分给一些小朋友,最多可以分给几个小朋友? 6、两个连续自然数的和是21,这两个数的最大公因数是(),最小公倍数是()。 7.为美化市容市貌,市政府决定对某地区进行整改,有一排电线杆,相邻两根电线杆之间的距离是45米,现在要改成相距都是60米,且起点那根电线杆不动。从起点开始到第一根不需移动的电线杆之间的距离是多少米? *六. 动脑筋,想一想: *1某数除以3、5、7时都余1,这个数最小是()。 *2)甲,乙,甲和乙的最大公因数是(),甲和乙的最小公倍数是()*3)学校买40支钢笔和50本练习本,平均奖给四年级三好学生,结果钢笔多4支,练习本多2本,三好学生有几人?

最大公约数的三种算法复杂度分析时间计算

理工大学信息工程与自动化学院学生实验报告 (2011 —2012 学年第 1 学期) 课程名称:算法设计与分析开课实验室:信自楼机房444 2011 年10月 12日 一、上机目的及容 1.上机容 求两个自然数m和n的最大公约数。 2.上机目的 (1)复习数据结构课程的相关知识,实现课程间的平滑过渡; (2)掌握并应用算法的数学分析和后验分析方法; (3)理解这样一个观点:不同的算法能够解决相同的问题,这些算法的解题思路不同,复杂程度不同,解题效率也不同。 二、实验原理及基本技术路线图(方框原理图或程序流程图) (1)至少设计出三个版本的求最大公约数算法; (2)对所设计的算法采用大O符号进行时间复杂性分析; (3)上机实现算法,并用计数法和计时法分别测算算法的运行时间; (4)通过分析对比,得出自己的结论。 三、所用仪器、材料(设备名称、型号、规格等或使用软件) 1台PC及VISUAL C++6.0软件 四、实验方法、步骤(或:程序代码或操作过程) 实验采用三种方法求最大公约数 1、连续整数检测法。

根据实现提示写代码并分析代码的时间复杂度: 方法一: int f1(int m,int n) { int t; if(m>n)t=n; else t=m; while(t) { if(m%t==0&&n%t==0)break; else t=t-1; } return t; } 根据代码考虑最坏情况他们的最大公约数是1,循环做了t-1次,最好情况是只做了1次,可以得出O(n)=n/2; 方法二:int f2(int m,int n) { int r; r=m%n; while(r!=0) { m=n; n=r; r=m%n; } return n; } 根据代码辗转相除得到欧几里得的O(n)= log n 方法三: int f3(int m,int n) { int i=2,j=0,h=0; int a[N],b[N],c[N]; while(i

最小公倍数最大公因数与两数的关系

学生已掌握两数的乘积等于两数的最大公因数与最小公倍数的乘积,但对于只知道两数中的一数及最小公倍数,求出另一数的情况不知从何下手。在五年级下册的数学典中点中已经出现此类题目,下面我将方法呈现如下: 已知两数的最小公倍数和其中一个数,如何求另一个数的做法及练习题和答案 例:已知36和另一个数的最小公倍数是144,问另一个数可能是多少? 方法:144÷36=4=2×2 36=2×2×3×3 用短除法分解质因数 144=2×2×3×3×2×2直接用36分解后的结果再乘以2个2就可以了 分解后,完全相同项(因数及其个数完全相同)为3×3,排除完全相同项后,最小公倍数剩下的是2×2×2×2=16,然后16不乘或分别乘以完全相同项的不同组合,得出结果。 所以,本题另一个数的可能性: (1)16 (2)16×3=48(3)16×3×3=144共三种。 再举个例子看一下 已知70与另一个数的最小公倍数是210,求另一个数可能是多少? 210÷70=3 70=2×5×7 210=2×5×7×3 另一个数可能是(1)3 (2)3×2 (3)3×5 (4)3×7 (5)3×2×5 (6)3×2×7 (7)3×5×7 (8)3×2×5×7 注:如果分解后没有完全相同项,则只有一种可能即最小公倍数。 例:12=2×2×3 72=2×2×3×2×3则另一数只能是72 练习题 1、已知27与另一数既不互质又不是倍数关系,且两数的最小公倍数是108,另一数可能是多少? 2、已知48与另一数的最小公倍数是144,另一数可能是多少? 3、已知24与另一数的最小公倍数是144,另一数是多少? 4、已知24与另一数的最小公倍数是96,另一数是多少? 5、已知36与另一数不是倍数关系,且它们的最小公倍数是108,求另一数是多少? 6、已知60与另一数的最小公倍数是120,求另一数。 答案: 1.27=3×3×3 108=3×3×3×2×2 另一数可能为(1)2×2因为不互质所以排除 (2)2×2×3=12 (3)2×2×3×3=36 (4)2×2×3×3×3=108因为不是不是关系所以也排除 所以另一数可能是12,和36. 2. 48=2×2×2×2×3 144=2×2×2×2×3×3

论最小公倍数和最大公约数的方法

论在小学教材中求最大公约数和最小公倍数的方法 班级:08数三班 学号:30308346 姓名:钟世校 初等数论是研究整数最基本性质的一门十分重要的数学基础课程,整除理论是初等数论的基础,其中心内容是最大公约数理论和算术基本定理,而我现在要论述的是求最大公约数和最小公倍数的几种方法 首先,让我们一起在来来了解一下最大公约数与最小公倍数的定义: 最大公约数: 设1a , 2a ,…,n a (n ≥2)是不全为零的整数,如果d| i a (i =1,2,3…,n),则称d 为 1a , 2a ,…,n a 的公约数,全体公约数中最大的一个数称为 1a , 2a ,…,n a 的最大公约数,记作(1a , 2a ,…,n a ). 最小公倍数: 设1a , 2a ,…,n a 是非零整数.若有整数M, 使 i a | M (i =1,2,3…,n ),则称 M 为1a , 2a ,…, n a 的公倍数,公倍数中最小的正数,称为1a , 2a ,…,n a 的最小公倍数,记作[1a , 2a ,…,n a ]。 求最大公约数的方法通常有两种,即用分解质因数法求最大公约数或用辗转相除法求最大公约数(亦称欧几里得算法),而求最小公倍数通常是用分解质因数或利用最大公约数来求最小公倍数,下最面我通过几道例题来演示上述方法. 一、 求最大公约数的方法. ⒈用分解质因数法求最大公约数. 例1. 求2700 、 7560、3960的最大公约数 解:把2700 、7560 、3960分别分解质因数. 得 2700=32 2 35 2?? 7560=3 3 357 2??? 3960= 2 3 352 11 ??? ∴ (2700,7560,3960)= 2 2 352 ??180 = 即2700 、 7560 、3960的最大公约数为180.

最大公约数和最小公倍数算法

C语言求最大公约数和最小公倍数算法假设求任意两个整数的最大公约数和最小公倍数,采用函数调用形式进行。 1、辗转相除法 辗转相除法(又名欧几里德法)C语言中用于计算两个正整数a,b的最大公约数和最小公倍数,实质它依赖于下面的定理: a b=0 gcd(a,b) = gcd(b,a mod b) b!=0 根据这一定理可以采用函数嵌套调用和递归调用形式进行求两个数的最大公约数和最小公倍数,现分别叙述如下: ①、函数嵌套调用 其算法过程为:前提:设两数为a,b设其中a 做被除数,b做除数,temp为余数 1、大数放a中、小数放b中; 2、求a/b的余数; 3、若temp=0则b为最大公约数; 4、如果temp!=0则把b的值给a、temp的值给a; 5、返回第第二步; 代码: int divisor (int a,int b) /*自定义函数求两数的最大公约数*/ { int temp; /*定义整型变量*/ if(a

C语言算法——最大公约数

基本算法——辗转相除法 问题:输出两个正整数a,b,且0 void main() { int a,b, p, q; do{ printf("请输入a和b:\n"); scanf("%d%d",&a,&b); } while ( a<0 || b<0 || a>b); p=a; while( a%p!=0 || b%p!=0) p--; printf("这两个数的最大公约数是%d\n",p); q=b; while( q%a!=0 || q%b!=0) q++; printf("这两个数的最小公倍数是%d\n",q); }

改进——已知整数a,b及其最大公约数p,则直接可推算出最小公倍数q: q= a*b/p; 源程序2 #include void main() { int a,b, p, q; do{ printf("请输入a和b:\n"); scanf("%d%d",&a,&b); } while ( a<0 || b<0 || a>b); p=a; while( a%p!=0 || b%p!=0) p--; printf("这两个数的最大公约数是%d\n",p); q= a*b/p; printf("这两个数的最小公倍数是%d\n",q); } 解法1的缺点:效率低。 例如a=1397, b=2413,其最大公约数p=127,为得到p,共循环了1397-127+1=1171次。如何提高效率?

相关主题