最大公约数2
《最大公约数》教学设计
公正九年制学校：杨芳
教学内容：九年义务教育五年制小学数学第八册《最大公约数》
教学目的：
1、理解公约数，最大公约数、互质数的意义。
2、能用列举法和短除法求两个数的最大公约数。
3、培养学生互助互让，团结进取的精神。
4、激发学生关心班级，热爱班级的情感。
教学重点：理解公约数，最大公约数，互质数的意义。
教学重点：用短除法求两个数最大公约数的方法。
教学方法；合作探究
教学过程：
一、创设情景，激发兴趣。
上课开始，我让同学们看一看老师给他们带来了什么礼物，同学们看到礼物后非常高兴，这时我告诉同学们这些奖品只能奖给这节课表现出色的同学，你们想得到吗？现在请同学们看一看老师的奖励原则。
多媒体演示：“猜一猜”
老师准备了29支铅笔和38本练习本平均奖给几个课堂表现出色的同学？老师这儿要剩下2只铅笔和2只练习本，你知道这节课最多有几个同学得奖吗？
同学们根据自己的生活实际与数学现实猜到不同答案。我没急于
告诉他们正确答案，而是说学了本节课知识后，同学们就能得到正确答案了。这节课我们共同研究最大公约数。
板书课题：最大公约数。
（这一部分设计的意图是：由学生获得奖品这一情境导入新课，有利于激发学生的好奇心，调动学生学习的积极性，增加学生注意力，并且密切了教学与生活的联系，激发了学生强烈的探究欲望。）
二、望文析义——猜想
师：看到了课题，你想到了什么？
生1：……生2：……同学们望文析义，会说出不同的理解内容。同学们说的是对是错呢？我们现在就开始研究。
（这一部分的设计意图是由学生提出问题，明确自主探究的学习目标，既创设了良好的学习情境，又激发了学生学习兴趣，提高了学习效果。）
一、生生互动，引发思维；
1、多媒体演示：8、1
2、44、11四个数，分组写出各数的约数。
2、组合。
师：把这些数两两组合，有几种不同的分组方法？学生回答后，我让学生补充说明组合方法。师：你们说的对吗？看屏幕。多媒体演示：“哇”8和12 8和44 8和11 12和44 12和和44看到多媒体演示；同学们也会随之“哇“的呼出声来。
（这一部分的设计意图主要是根据新课标要求，要将不同课时内容有机的组合在一起。高效率地完成教学任务。我针对这一要求，就
将组合的原理引入课堂，培养了学生思维的全面性与条理性。同时也为下面的教学奠定了基础。）
3、下面我们以8和12为例，研究什么是最大公约数，请同学们先独立思考，然后再小组交流。
多媒体出示思考问题：8和12各有哪些约数？它们公有的约数有哪几个？其中最大的约数是几？在学生独立思考小组交流的基础上，总结出探究实践的三个步骤。在学生回答的同时，多媒体随机显示：
1、分别列出8和12的约数。
2、找出8和12公有的约数。
3、找出8和12的最大公约数。
（这一部分设计意图是用多媒体演示学生的思维过程，并用不同色调，不同声音，不同形式显示出来，使学生体会到一种“美”的享受。引发了学生学习兴趣。并在学习过程中先独立思考，养成学习习惯，并清楚明确了自己的知识水平，然后再小组交流，让学生互相启发，互相完善，共同发展，也在发展个人见解的同时，使学生张扬个性，体验成功，建立自信，在学习过程中传递着爱心，促进了人与人之间的交流。）
4、用集合的形式，多媒体演示8和12的最大公约数的求解过程。
5、分小组合作，找出第（2）——（6）组任意组两个数的公约数和最大公约数。
6、概括出公约数、最大公约数的概念
（这一部分的设计意图是用表格出示便于观察，利于思考，使抽
象思维变为具体，小组自选内容再次突出学生主体地位，这不但体现了新课标的思想，更主要是创设了一种和谐、宽松的课堂氛围。老师在课堂上真正作为了引导者，推动者和思考者，学生在讨论交流，合作探究中学习知识。感受体验到了学数学的乐趣。）
7、概括互质数的概念。
师：请同学们观察屏幕上每组中的公约数，根据公约数个数的多少，以上各组可以分为几类。
生A：……生B：……生C：……
师：老师发现几种分类方法都有一个共同的特点，都是把公约数只有一个的作为一类，观察公约数只有一个的几组，你发现了什么？
引导学生回答出：它们的公约数都是1。
师：公约数只有1的两个数叫做互质数。
师：现在请同学们看一看胸前的学号，同桌间判断两个学号是不是互质数？
学生判断之后，师问学生：“你们知道老师的号码吗？“
有的学生大胆说出：“老师是46号，因为我们班有45名学生，我们是一个集体，你的号码一定是46号。”
我对学生的回答给予充分的肯定，胸前也戴上了号码。接着让学生判断老师的号码与你们的号码是互质数吗？
（这一部分仍然是让学生观察得到互质数的概念，明确互质数的特征。同时以学号的形式进行练习，既巩固了这部分知识，同时也对学生进行了热爱集体，关心集体的思想品德教育，也使学生感受到数
学就在身边，体现了数学源于生活，身边处处有数学的思想。）
8、探求用短除法求最大公约数的方法。
师：刚才大家知道什么是最大公约数，你们还想知道其它求最大公约数的方法吗？现在请同学们打开书自学这部分知识，然后小组讨论。
学生讨论后进行板演汇报。
（这一部分运用自学合作的教学手段，意在创设和谐愉悦的课堂氛围，减少学生的心理压力，充分发挥学生的主体性，让学生与教师之间，学生与学生之间，通过自学、合作进行研讨与探究，从而促进学生主动的发展，培养学生合作意识，创新精神和实践能力，另外小组合作学习，使学生都有了充分展示自己，表现自我的机会，连平时不善于表现的同学，也能体验三、层层深入，解决实际问题。
多媒体出示练习题：
一、求下面每组数的最大公约数
12和20 16和12 42和54 30和45
二、判断：
1、两个不同的质数一定是互质数。
2、如果两个数互质，它们没有公约数和最大公约数。
3、相邻的两个自然数一定是互质数。
4、两个合数一定不是互质数。
5、最小的合数和最小的质数这两个数不是互质数。
三、填空
1、A=2×3×5，B=2×3×7，A和B的最大公约数是（）。
2、两个数为互质数，这两个数的最大公约数是（）。
3、所有自然数的公约数是（）。
4、1和a（a为大于1的自然数）的最大公约数是（）。
5、甲数=2×5×a乙数=2×3×a，甲数与乙数的最大公约数是22，则a等于（）。
四、回到前面“猜一猜”多媒体出示“I SEE！”
“老师准备了29支油笔和38本笔记本，平均奖给几个课堂表现出色的同学，结果油笔多了2支，笔记本多了2本，你知道这节课最多有几个同学得到奖品吗？”
学生解答完这道题以后，并让学生举出生活中求最大公约数的问题。
五、打电话：多媒体出示“你记住了吗？”
1、既是5的倍数又是5的约数。
2、7和14的最大公约数。
3、既有约数2又能被3整除的一个最小合数。
4、最小的合数。
5、只有3个约数的奇数。
6、最小的既是奇数又是质数的数。
7、3和18的最大公约数。
8、两个连续自然数的约数的7倍。
（这一部分通过富有情趣多式多样的练习和活动，帮助学生巩固掌握本节课所学的知识，解决简单的实际问题，并让学生从实际出发，根据要解决问题的条件，做全面分析，周密思考，提高了学生全面分析及解决实际问题的能力，培养了学生的创造精神，并在打电话的练习中增进了师生感情，解决了实际问题。）
三、情感体验
同学们，这节课你们开心吗？你们有什么收获？老师也非常高兴，老师希望同学们在今后的学习中，多观察、多思考去做生活中的有心人。
（这一部分是学生学习的一种激励评价，使学生体验到主动探索，获取知识的喜悦，激发了学生学习兴趣，树立了学习的自信心，增强了动脑思考的能力。）
最大公约数教学设计
《最大公约数》教学设计 张海燕 教学内容： 人教版小学五年级教科书第66---68页例1、例2及做一做。 教学目标： 1.使学生理解公约数、最大公约数、互质数的概念及求两个数的最大公约数的一般方法。 2.让学生经历求两个数的最大公约数的算理和算法研究过程，培养学生的观察、分析、推理和概括能力。 3.让学生在探索求两个数的最大公约数的方法的过程中，获得探索发现的积极体验，培养学生科学研究问题的意识。 教学重点： 理解公约数、最大公约数、互质数的概念. 教学难点： 掌握求两个数的最大公约数的一般方法. 教学步骤： 一、设情引入 老师有一个问题，同学们愿意帮助解决吗？有一张长30厘米、宽12厘米的长方形彩色纸，要把它剪成最大的正方形，不能有余剩，能剪多少个呢？ 解决这个问题要用到我们今天学习的知识，通过今天的学习，老师相信同学们一定能解决这个问题。 板书课题：最大公约数 说出什么是约数？ 二、探究新知 (一)教学例1 1.感知公约数和最大公约数 8和12各有哪些约数，它们公有的约数有哪几个?最大的公有的约数是多少?
板书：8的全部约数：1、2、4、8 12的全部约数：1、2、3、4、6、12 学生交流：发现了什么? 学生汇报：8和12公有的约数是：1、2、4，最大的公有的约数是：4 8和12公有的约数，还可以用圈的形式表示。 8的约数 12的约数 8和12的公有的约数 2.总结概念 通过刚才的探索，你能说一说什么叫公约数？什么叫最大公约数？ 3.反馈练习： 把15和18的约数、公约数分别填在下面的圈里再找出它们的最大公约数. (二)理解互质数 1.5和7的公约数和最大公约数各是多少?7和9呢? 5的约数：1、5 7的约数：1、7 7的约数：1、7 9的约数：1、3、9 5和7的公约数：1 7和9的公约数：1 5和7的最大公约数：1 7和9的最大公约数：1 教师提问：有什么共同点?(公约数和最大公约数都是1) 教师点明：公约数只有1的两个数，叫做互质数. 2.学生讨论：8和9是不是互质数，为什么? 强调：判断两个数是不是互质数，只要看这两个数的公约数是不是只有1. 3.分析：质数和互质数有什么不同? (意义不同，质数是对一个数说的，互质数是对两个数的关系说的.) 4.反馈练习：学生举例说明互质的数. (三)教学例2 通常我们用分解质因数的方法来求两个数的最大公约数。 求18和30的最大公约数.
最大公约数与最小公倍数(正式)
最大公约数与最小公倍数 基本概念： 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。 3、最大公约数与最小公倍数的求法 A．最大公约数 求两个数的最大公约数一般有以下几种方法 （1）分解质因数法 （2）短除法 （3）辗转相除法 （4）小数缩倍法 （5）公式法 前两种方法在数学课本中已经学过，在这里我们主要介绍辗转相除法。 当两个整数不容易看出公约数时（一般是数字比较大），我们可以合用辗转相除法。B．最小公倍数 求几个数的最小公倍数的方法也有以下几种方法： （1）分解质因数法 （2）短除法 （3）大数翻倍法 （4）a×b=（a,b）×[a,b] 上面的公式表示：两个数的乘积等于这两个数的最大公约数和最小公倍数的乘积。 例1、437与323的最大公约数是多少？
LX1、24871和3468的最小公倍数是多少？ 例2、把一块长90厘米，宽42厘米的长方形铁板剪成边长都是整厘米，面积都相等的小正方形铁板，恰无剩余。至少能剪块。 【分析】根据题意，剪得的小正形的边长必须是90和42的最大公约6。所以原长方形的长要分90÷6＝15段，宽要分42÷6＝７段，至少能剪17×７＝105（块） 解：（１）求90和42的最大公约数 2 90 42
最大公约数的三种算法 复杂度分析 时间计算
昆明理工大学信息工程与自动化学院学生实验报告 （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 最大公约数 教学目标 1．使学生掌握公约数、最大公约数、互质数的概念． 2．使学生初步掌握求两个数的最大公约数的一般方法． 教学重点 理解公约数、最大公约数、互质数的概念． 教学难点 掌握求两个数的最大公约数的一般方法． 教学步骤 一、铺垫孕伏． 1．说出什么是约数、质因数、分解质因数． 2．求18、20、27的约数 3．把18、20、27分解质因数 二、探究新知． 教师引入：我们已经会求一个数的约数了，这节课我们学习怎样求两个数公有的约数．（一）教学例1【演示课件“最大公约数”】 8和12各有哪些约数，它们公有的约数有哪几个？最大的公有的约数是多少？ 板书：8的全部约数：1、2、4、8 12的全部约数：1、2、3、4、6、12 学生交流：发现了什么？ 学生汇报：8和12公有的约数是：1、2、4 最大的公有的约数是：4．（教师板书） 1．总结概念：8和12公有的约数，叫做8和12的公约数． 1、2、4是8和12的公约数．公约数中最大的一个叫做最大公约数，4是8和12的最大公约数． 2．阅读教材，理解公约数、最大公约数的意义． 3．反馈练习：把15和18的约数、公约数分别填在下面的圈里再找出它们的最大公约数． （二）教学互质数【演示课件“互质数”】 1．5和7的公约数和最大公约数各是多少？7和9呢？ 5的约数：1、5 7的约数：1、7 7的约数：1、7 9的约数：1、3、9 5和7的公约数：1 7和9的公约数：1 5和7的最大公约数：1 7和9的最大公约数：1 教师提问：有什么共同点？（公约数和最大公约数都是1） 教师点明：公约数只有1的两个数，叫做互质数． 2．学生讨论：8和9是不是互质数，为什么？ 强调：判断两个数是不是互质数，只要看这两个数的公约数是不是只有1． 3．分析：质数和互质数有什么不同？ （意义不同，质数是对一个数说的，互质数是对两个数的关系说的．） . 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． 名思小学奥数训练题库约数与最大公约数13712345678987654321的除本身之外的最大约数是多少？ 138将一个两位数的十位数字减去或加上它的个位数字，所得到的两个数都是78的大于1的约数。求这个两位数。 139有一个自然数，它的最小的两个约数之和是4，最大的两个约数之和是100，求这个自然数。 140有一个自然数，它的最大的两个约数之和是123，求这个自然数。 141求只有 8个约数但不大于30的所有自然数。 142给出一个自然数n，n的所有约数的个数用T(n)表示。(1)求 T(42)；(2)求满足 T(n)=8的最小自然数n；(3)如果T(n)=2，那么n是怎样的数？ 143在1～100中，所有的只有3个约数的自然数的和是多少？ 144如果自然数a和b各自恰好都有5个不同的约数，那么a×b能否恰好有10个不同的约数？ 145☆少年宫游乐厅内悬挂着200个彩色灯泡，这些灯泡或明或暗，十分有趣。这200个灯泡按1～200编号，它们的亮暗规则是： 第一秒，全部灯泡变亮； 第二秒，凡编号为2的倍数的灯泡由亮变暗； 第三秒，凡编号为3的倍数的灯泡改变原来的亮暗状态，即亮的变暗，暗的变亮； 一般地，第n秒凡编号为n的倍数的灯泡改变原来的亮暗状态。 这样继续下去，每4分钟一个周期。问：第200秒时，明亮的灯泡有多少个？ 146100以内约数个数最多的自然数有五个，它们分别是几？ 147一个学生做两个两位数乘法时，把其中的一个乘数的个位数字9误看成7，得出的乘积是756。问：正确的乘积是多少？ 148给出一个自然数n，n的所有约数的和用S(n)表示，求S(24)和S(36)。 149☆对于任意的大于2的自然数n，所有小于n且与n互质的自然数的个数是奇数还是偶数，还是不能肯定？ 算法设计与分析 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．使学生掌握公约数、、互质数的概念．2．使学生初步掌握求两个数的的一般方法．教学重点理解公约数、、互质数的概念．教学难点掌握求两个数的的一般方法．教学步骤一、铺垫孕伏．1．说出什么是约数、质因数、分解质因数．2．求18、20、27的约数3．把18、20、27分解质因数二、探究新知．教师引入：我们已经会求一个数的约数了，这节课我们学习怎样求两个数公有的约数．（一）教学例1【演示课件“”】8和12各有哪些约数，它们公有的约数有哪几个？最大的公有的约数是多少？板书：8的全部约数：1、2、4、8 12的全部约数：1、2、3、4、6、12 学生交流：发现了什么？ 学生汇报：8和12公有的约数是：1、2、4 最大的公有的约数是：4．（教师板书）1．总结概念：8和12公有的约数，叫做8和12的公约数．1、2、4是8和12的公约数．公约数中最大的一个叫做，4是8和12的．2．阅读教材，理解公约数、的意义．3．反馈练习：把15和18的约数、公约数分别填在下面的圈里再找出它们的． （二）教学互质数【演示课件“互质数”】 1．5和7的公约数和各是多少？7和9呢？ 5的约数：1、57的约数：1、7 7的约数：1、79的约数：1、3、9 5和7的公约数：17和9的公约数：1 5和7的：17和9的：1 教师提问：有什么共同点？（公约数和都是1） 教师点明：公约数只有1的两个数，叫做互质数． 2．学生讨论：8和9是不是互质数，为什么？ 强调：判断两个数是不是互质数，只要看这两个数的公约数是不是只有1． 3．分析：质数和互质数有什么不同？ （意义不同，质数是对一个数说的，互质数是对两个数的关系说的．）4．反馈练习：学生举例说明互质的数． （三）教学例2． 求18和30的． 1．用短除法把18和30分解质因数． 2．教师提问：根据结果能否知道18和30的约数各有哪些？怎么想的？ 明确：根据分解质因数的方法可以求一个数的约数．3．师生归纳：18和30的约数，要能整除18，又能整除30，就必须包含18和30公有的质因数．是公约数中最大的，它就必须包含18和30全部公有的质因数2和3．2×3＝6，所以18和30的是6．4．教学求的一般书写格式．启发：为了简便能不能边分解质因数边找公有的质因数？（把两个短除式合并） 最大公约数和最小公倍数练习题 一. 填空题。 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本，四年级有多少名三好学生，他们各得到什么奖品？ “最大公约数”练习题姓名 基础题 一、在下圈内填上适当的数二、70=2×5×7 30=2×3×5×11 70和330相同的质因数是（）， 70和330的最大公约数是（） 三、（1）24的约数有（），（2）36的约数有（）（3）24和36的公约数有（），（4）24和36的最大公约数有（）四、先把下面两个数分别分解质因数，再求它们的最大公约数。 165=（）×（）×（）195=（）×（）×（）165和195的最大公约数是（）×（）=（） 五、在3、10、18、19、35五个数中： （1）两合数（）和（）是互质数，它们的最大公约数是（）。 （2）两合数（）和（）有公约数5，所以它们不是互质数。 （3）（）和（）是两个不同的质数，一定是（）。 （4）质数（）和合数（）成倍数关系，因此它们的最大公约数是（）。拓展题 一、判断题（对的在括号内打V，错的打X） （1）因为数a和数b是互质数，所以数a和数b没有公约数。（）（2）因为b是a和b的公约数，所以b也是a和b的最大公约数。（）（3）互质的两个数不一定都是质数（）；（4）两个质数的和一定还是质数。（）二、求下面每一组数的最大公约数（用短除法） （1）48和60 （2）55和66 （3）52和39 （4）242和66 （5）14、28和84 （6）18、24、和42 （7）3、7和5 三、直接写出下面每组数的最大公约数 1和9 15和5 6和7 105和315 28和27 11和33 13和17 100和101 四、把长102厘米，宽78 厘米的硬纸，剪成同样大的正方形，并且不能剩余， 剪得正方形边长最长是多少？可以剪成几块？ 五、某班有男生24人，女生16人，在参加植树活动中将全班同学分成若干小组， 要求每组中男生人数相等，女生人数也相等，最多可以分成多少组？每组男女生共有几人？ 六、已知两数积是1734，它们的最大公约数是17，求这两个数。 七、有三根铁丝，一根长7米，一根长20米，一根长30米，要把它们截成同样 长的小段，已知第一根余下1米，第二根余下2米，第三根没有剩余，每段最长多少米？ 综合题 一、填空题 1．有四个（可以相同）小于10的自然数，它们的积是360，已知四个数中只有一个是合数，那么这四个数是（）。 2．最小的自然数，最小的质数，最小的合数之和的2倍是（）。 3．一个数，千位上是最小的质数，百位上是最小的自然数，个位上是最小合数，百分位上是最大数字，其余数位上的数字都是零，这个数应写作（）。4．直接写出下面各组数的最大公约数在括号内。 4和9（）18和9（）2和14（）3和70（）22和33（）21和35（） 5．已知两个数的和是256，它们的最大公约数是16，这两数是（）和（）；（）和（）；（）和（）；（）和（）。 二、判断题 1．任何一个自然数减1，还是个自然数---------------------------------------（）2．12和18的公约数只有3个（）3．同任何非零自然数互质的数是1（）4．奇数不一定是质数，偶数都是合数（）5．互质的两个数没有最大公约数（）6．如果一个非零自然数a小于某个质数b，那么a与b一定互质--------------（）三、选择。 1．a＝2×2×5，b＝2×3×5，a、b最大公约数是（）。 A 2 B 5 C 10 D 15 E 6 2．甲数是乙数的15倍，这两个数的最大公约数是（）。 A 15 B 甲数 C 乙数 D 甲数×乙数 3．两个自然数的最大公约数是12这两个数的全部公约数是（）。 A 1、2、3、12 B 2、3、4、6 C 2、3、4、6、12 D 1、2、3、4、6、12 4．下面哪句话是错的（）。 A 4是16的约数 B 2是质数 C 9是合数 D 两个互质数没有公约数 最大公约数和最小公倍数的比较 教学目标 (一)进一步理解并掌握最大公约数和最小公倍数的概念，分清求最大公约数和最小公倍数的相同点和不同点。 (二)培养学生仔细、认真的做题习惯和比较的思维方法。 (三)培养学生观察、分析、比较的能力。 教学重点和难点 最大公约数和最小公倍数异同点的比较。 教学用具 教具：小黑板，投影片。 学具：判断卡，选择卡。 教学过程设计 (一)复习准备 教师： ①什么叫最大公约数和最小公倍数？ ②怎样求最大公约数和最小公倍数？ ③求下面各题的最大公约数和最小公倍数？(口答) 8和1613和262和97和15 教师：对上面几道题你是怎么想的？各有什么特点？你能发现什么规律？ 明确： ①两个数有倍数关系，最大公约数最较小数，最小公倍数是较大数。 ②两个数互质，最大公约数是1，最小公倍数是两个数乘积。 (二)学习新课 1．出示例5。 求28和42的最大公约数和最小公倍数。(要求学生独立完成。) 学生口述教师板书。 28和42的最大公约数是： 2×7=14 28和42的最小公倍数是 2×7×2×3=84 教师：观察上面两道题，谁能说出求最大公约数和求最小公倍数有什么地方相同？什么地方不同？(讨论) 在讨论的基础上，总结出下面的结论。 教师：为什么求最大公约数只要把所有除数乘起来，而求最小公倍数就要把所有除数和商都乘起来呢？ 明确：求最大公约数是两个数公有质因数的积；求最小公倍数既要包含两个数公有质因数，又要包括各自独有的质因数。 教师：既然求两个数的最大公约数和最小公倍数的短除过程是相同的，那么，我们就可以用一个短除式来表示。例5怎样做简便？(由学生 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、甲＝2×3×5，乙＝2×3×7，甲和乙的最大公约数是（）． 2、36和60相同的质因数有（），它们的积是（），也就是36和60的（）． 3、（）的两个数，叫做互质数． 4、自然数a除以自然数b，商是15，那么a和b的最大公约数是（）． 二、判断（对的打“√”，错的打“×”）． 1、互质数是没有公约数的两个数．（） 2、成为互质数的两个数，一定是质数．（） 3、只要两个数是合数，那么这两个数就不能成为互质数．（） 4、两个自然数分别除以它们的最大公约数，商是互质数．（） 三、选择题 1、成为互质数的两个数（）． ①没有公约数②只有公约数1 ③两个数都是质数④都是质因数 2、下列各数中与18互质的数是（）． ①21 ②40 ③25 ④18 3、下列各组数中，两个数互质的是（）． ①17和51 ②52和91 ③24和25 ④ 11和22 四、直接说出下列各组数的最大公约数． 1、8与9的最大公约数是（）． 2、48、12和16的最大公约数是（）． 3、6、30和45的最大公约数是（）． 4、150和25的最大公约数是（）． 习题精选（二） 一、填空 1、按要求，使填出的两个数成为互质数． ①质数（）和合数（）， ②质数（）和质数（）， ③合数（）和合数（）， ④奇数（）和奇数（）， ⑤奇数（）和偶数（）． 2、两个数为互质数，这两个数的最大公约数是（）． 3、所有自然数的公约数为（）． 4、18和24的公约数有（），18和24的最大公约数是（）． 二、判断（对的打“√”，错的打“×”）． 1、因为 15÷3＝5，所以15和3的最大公约数是5．（） 2、30 、15和5的最大公约数是30．（） 3、最小的合数和最小的质数这两个数不是互质数．（） 4、相邻的两个自然数一定是互质数．（） 三、选择题 最大公约数和最小公倍数怎么求？ 首先把两个数的质因数写出来，最小公倍数等于它们所有的质因数的乘积（如果有几个质因数相同，则比较两数中哪个数有该质因数的个数较多，乘较多的次数）。 比如：求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．三种数量不等的茶叶价值相等，等分装袋后，每袋价值仍相等，由于每种茶叶的总价值相等，每袋价值也要相等，所以这三种茶叶分装的袋数也一定相同．为了使每袋价值最低，就应使袋数尽可能多， 理工大学信息工程与自动化学院学生实验报告 （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 最大公约数优秀教案 导读：本文最大公约数优秀教案，仅供参考，如果觉得很不错，欢迎点评和分享。 最大公约数优秀教案 教学目标 1、结合解决问题理解公因数和最大公因数的意义，学会求两个数的最大公因数的方法。 2、在探索公因数和最大公因数意义的过程中，经历观察、猜测、归纳等数学活动，进一步发展初步的推理能力。在解决问题的过程中，能进行有条理、有根据地进行思考。 3. 学会用公因数、最大公因数的知识解决简单的现实问题，体验数学与生活的密切联系。 教学重点：理解公因数与最大公因数的意义，用短除法求最大公因数的方法。 教学难点：找公因数和最大公因数的方法。 学具准备：若干张长24 厘米，宽18 厘米的长方形纸；若干张边长1 ―7 厘米的各种正方形纸。 教学过程： 一、创设情境，提出问题。 1、出示剪纸艺术图片，导入新课。 师：同学们，你们见过剪纸作品吗？下面请看大屏幕。 师：漂亮吗！ 师：剪纸是我国传统的民间艺术之一，具有很强的普及性、装饰性和趣味性。（板书：剪纸中的数学） 2、出示情景图，发现信息，提出问题。 师：请同学们认真观察情境图，你们都看到了什么？ 生1 ：4 位小朋友在剪纸。 生2 ：他们已经剪成4 幅漂亮的正方形纸花了。 生3 ：长方形纸的长是18 厘米、宽是12 厘米。 生4 ：要求把这张长方形的纸剪成边长是整厘米的正方形。 生5 ：剪完后没有剩余。 生6 ：正方形的边长可以是几厘米呢？ 二、合作探讨，理解意义，学习方法。 1、演示课件，指导操作方法。 师：同学们说的真好！要将长24 厘米、宽18 厘米的长方形纸剪成正方形纸，没有剩余，边长可以是几厘米？请同学们猜想一下。 生：边长可以是1 厘米、2 厘米、3 厘米等。 师：怎样验证你们的猜想呢？ 生：拿正方形纸片摆一摆。 师：你的方法很好，我们可以先选用边长1 厘米的正方形来摆摆看，有没有剩余。请看屏幕。（课件演示过程） 师：长方形的长有没有剩余？长方形的宽有没有剩余？ 师：通过刚才的观察，用边长1 厘米的正方形摆，有没有剩余？ ?最大公约数和最小公倍数练习题 一. 填空题。 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、理解和掌握公约数和最大公约数、互质数的概念；会根据概念求最大公约数； 2、知道互质数是指两个数的关系，会判断两个数是不是互质数，掌握互质数的三种特殊情况； 3、训练思维的有序性和条理性。 教学重难点：理解公约数和最大公约数的意义，以及互质数的意义。 教学准备：1-48号号码纸、小黑板 教学过程： 一、导入： 1、请同学们各自写出自己学号的约数。（学生动手练习） 2、谁的学号只有一个约数的，请举手。你是几号？（1号）1的约数只有1。 3、只有两个约数的是哪些同学？这些数叫什么数？（质数）质数的约数只有2个。 4、剩下的同学你们的约数有几个？都是什么数？（合数）合数的约数至少有三个。 [复习铺垫时先给学生编号，让学生写出各自号码的约数。复习约数、质数合数的目的是加强新旧知识间的联系，为学好新知作好铺垫，为顺利导入新课，突破难点打好基础。] 二、公约数和最大公约数的教学 1、请学号是12的同学走上前来。汇报一下12所有的约数。 （板书：12的约数有：1、12、2、6、3、4） 请学号是1、2、3、4、6的同学站到12的旁边，1、2、3、4、6、12都是12 的约数。 2、请学号是30的同学走上前来，汇报一下30所有的约数。 （板书：30的约数有1、30、2、15、3、10、5、6。） 请学号是1、2、3、5、6、10、15的同学站到30的旁边，1、2、3、5、6、10、15、30都是30 的约数。 3、刚才我们把12和30的约数都找到了前面，这边是12的约数，（故意地）你的约数怎么只有4和12了呢？怎么不把你的约数看好呢？ （学号是12的同学和约数是30 的同学挣抢学号是1、2、3、6的这几位同学） 全班同学一起来做个裁判，1、2、3、6这几位同学到底该站在哪边呢？ （学生争议） 生：我觉得站在他们两个数的中间比较好。 师：为什么？请说出理由。 师：像这样1、2、3、6几个约数，可以给他们起个什么名称呢？ 生：叫公约数吧。 4、（明确指出）1、2、3、6就是12和30 的公有约数，我们称它们是12和30 的公约数。6是其中最大的一个，叫12和30 的最大公约数。 板书：12和30的公约数有：1、2、3、6 5、说一说什么叫做公约数？什么叫做最大公约数？ 出示概念。刚刚我们是怎么找到12和30的公约数的？ 6、请按照刚才的方法，找出下列各组数的公约数和最大公约数 （1）16和24 16的约数有： 24的约数有： 16和24的公约数有最大公约数是： （2）15和18 15的约数有： 18的约数有： 15和18的公约数有最大公约数是： （3）8和9 公约数有：最大公约数是： （4）1和12 公约数有：最大公约数是： （5）3和7 公约数有：最大公约数是： （6）4和5 公约数有：最大公约数是： [联系实际，初步感知：为了使学生初步感知公约数和最大公约数的意义，充分发挥学生的主观能动性，设计了学生活动，把12和30的约数同 公约数与最大公约数教学设计 一、情景导入 课件：出示长30分米，宽24分米的长方形。 师：同学们，今天老师请大家帮一个忙，老师有一间厨房要铺地砖，看大屏幕，这就是厨房的形状，长30分米，宽24分米，请同学们协助老师选一选用多大的正方形地砖铺地，才能铺得既整齐又节约呢？告诉老师正方形的边长是几？ 生：1、2、3、6分米。 师：如果老师还想铺快点，你认为哪一种方法最好？ 生：6分米。 师：同学们是怎样想到用边长1、2、3、6分米的正方形在砖铺地砖铺地的？ 生：这些数既是30的约数又是24的约数。 师：同学们的回答是准确的，为什么准确呢？这就是我们这节课将要探讨的内容。 板书：最大公约数 二、新课 师：同学们8的约数有哪些？ 生：1、2、4、8。 师：12的约数有哪些？ 生：1、2、3、4、6、12。 师：请同学们观察一下哪些是8和12公有的约数？ 生：1、2、4。 师：我们把8和12公有的约数1、2、4叫做8和12的公约数。 师：这些公约数中，谁最大？ 生：4。 师：4就是8和12的最大公约数。 师：通过刚才的探索，你能说说什么是公约数，什么是最大公约数。 生：说概念。 师：好，12个数公有的约数叫做这几个数的公约数。其中最大的一个，叫做这几个数的最大公约数。 师：好，看大屏幕，请同学们齐读一遍。 师：当然8除的公约数外，8还有独有的约数8，12还有独有的约数，3、6、12。 师：下面请同学们找出15和18的公约数，再找出它的最大公约数。 师：15的约数有哪些？ 生：…… 师：18的约数有哪些？ 生：1、2、3、6、9、18。 师：15和18的公约数有哪些？ 基本算法——辗转相除法 问题：输出两个正整数a,b,且0 改进——已知整数a,b及其最大公约数p,则直接可推算出最小公倍数q： q= a*b/p; 源程序2 #include 最大公约数
最大公约数的算法
2020小学奥数训练题库约数与最大公约数
matlab最大公约数 三种算法
最大公约数_教案教学设计_1
最大公约数与最小公倍数练习题
“最大公约数”练习题(基础教学)
最大公约数和最小公倍数的比较_教案教学设计
Java算法最大公约数和最小公倍数
《找最大公因数》习题(附答案)
最大公约数和最小公倍数怎么求
最大公约数的三种算法复杂度分析时间计算
最大公约数优秀教案
(完整版)最大公约数与最小公倍数练习题
最大公约数
公约数与最大公约数 教学设计
C语言算法——最大公约数