最大公约数-最大公约数

发布时间：2017-12-26 所属栏目：言论自由的算法

一 : 最大公约数

教学目标

(一)理解公约数，和互质数的意义。

(二)会用排列约数的方法和集合圈的方法，找两个数的公约数和。渗透集合思想。

(三)培养学生观察、比较、分析概括的能力。

教学重点和难点

(一)公约数、、互质数的意义。

(二)互质数与质数的区别。

教学用具

投影片。

教学过程设计

(一)复习准备

提问：说出24的全部约数；请将24分解质因数。说一说24的约数与质因数有什么区别？(约数可以是质数也可以是合数，质因数必须是质数。)

教师：前面我们复习了找一个数的约数和把一个合数分解质因数，它们都是研究的一个数的约数，今天要研究两个数的约数。

(二)学习新课

1．公约数和。

(1)板书例1，8和12各有哪些约数，它们公有的约数是哪几个？最大的公有的约数是多少？

学生口答教师板书：

8的约数有(1，2，4，8)。

12的约数有(1，2，3，4，6，12)。

8和12公有的约数有(1，2，4)。

8和12的最大的公有的约数有(4)。

教师：下面用集合图表示。(出示活动抽拉投影片)

(2)教师：第二幅中阴影部分表示什么？(8和12公有的约数，4是最大的。)

教师：1，2和4是8和12公有的约数，我们称它们是8和12的公约数，(板书：公约数) 4是其中最大的一个，叫做8和12的。(板书：。)

教师：说一说什么叫公约数？什么叫？

学生口答后，教师针对上述概括中“两个数”提问；有时我们要找的不是两个数公有的约数，可能是三个数，四个数等，那怎么说更准确？(把“两个数”换为“几个数”。)

请学生再次口述什么是公约数和，老师把板书补充完整：

几个数公有的约数，叫做这几个数的公约数；其中最大的一个，叫做这几个数的。

教师：我们研究两个数的约数，主要研究它们的公约数，尤其是。这节课的课题就是它。(板书课题：。)

2．练习。

(1)口答填空：(投影片)

12的约数是( )；

18的约数是( )；

12和18的公约数是( )；

12和18的是( )。

(2)把15和18的约数、公约数分别填在下面的集合圈里，再找出它们的。(同学们填在书上66页，请一两位同学填在投影片上、集体订正。)

3．认识互质数。

(1)教师板书：请找出下面各组数的公约数：

5和7(1) 8和9(1) 1和12(1)

9和15(1，3) 7和9(1) 16和20(1，2，4)

学生口答后老师在每组后面标出公约数。

教师：观察板书，根据公约数的情况，可以把这几组数分几类？各类的特点是什么？

学生口答，老师在公约数只有1的几组数下划上红线。并板书出：公约数只有1。

教师：(指着划上红线的几组数)公约数只有1的两个数叫做互质数。(将前面板书补充完整)如7和9就是互质数。

教师：请说一说这几组数中谁与谁互质(或谁与谁是互质数)。

教师：请举出两组互质数。

(2)请同学们讨论下面几个问题：

①任意写两个质数，看它们是不是互质数？

②任意写出两个相邻的自然数，看它们是不是互质数？

③任意写一个自然数，看它与1是不是互质数？

学生讨论后，肯定上述三种条件下得出的都是互质数。

教师：说一说你是用什么方法判定它们是互质数的？(要求说出自己的具体例子)

教师：你们所举的例子，都采用找它们的公约数的方法来判断它们是不是互质数。在今后的学习中，经常需要判断两个数是否互质，掌握了这三种情况下一定是互质数，就可以帮助我们很快作出判断。但是要注意，互质数不止这三种情况，如7和9，所以在作判断时最根本的方法是要看这两个数的公约数是不是只有1。

(3)想一想，以前学过的质数，与今天学习的互质数有什么区别？(质数所指是一个数，它的约数只有1和本身，互质数所指是指两个数，它们的公约数只有1。)

教师在板书“互质数”的“互”字下面标出红色的符号，问：这“互”字如何理解？

学生口答后，教师再次提示，说互质数一定要说出谁与谁互质。

(三)巩固反馈

1．口答填空：(投影片)

24的约数是( )；

36的约数是( )；

54的约数是( )；

24，36和54的公约数是( )；

24，36和54的是( )。

2．直接说出下面各组数的。

3和4 6和24 13和39

18和1 17和19 14和15

15和30 9和10 16和18

3．说出上题中哪几组是互质数。

(四)课堂总结与课后作业

1．公约数，，互质数。

2．作业：课本69页练习十四 1，2，3。

课堂教学设计说明

本节内容是在学生掌握了约数、质数、分解质因数等基础上进行的。公约数、的概念，在学生通过排列约数的办法认识后，又用集合图来表示，这样既渗透了集合思想，同时又使学生加深了对公约数，两个概念的理解。在学生掌握了这两个概念后，利用练习，引导学生进行观察分析，认识互质数的特点，采用讨论的形式，让学生自己去发现互质数中的最常见的三种情况，这样可以加深学生对互质数的理解，也提高了他们判断互质数的能力，最后安排了对容易混淆的质数与互质数进行对比区别，再次加深了对互质数概念的理解。

新课教学分三部分。

第一部分学习公约数、的意义，共分两层。通过排列约数和集合图，理解认识公约数，的意义；归纳两个概念。

第二部分是练习巩固新学概念。

第三部分学习互质数。分三层。认识互质数；掌握常见的三种情况；区分质数与互质数。

板书设计

二 : 最大公约数(gcd):Euclid算法证明及其它

在刚进大学学习C语言的时候，用的是谭浩强的那本“经典”教程（之所以加引号是在接触了更多的书籍和经过了高手的指点后，发现它算不上绝对的经典，但是是入门很好的书）。[www.61k.com］记得好像是在函数那一章的课后习题的第一题让写一个求两个数最大公约数的方法。因为当时是第一次接触C语言不知道这一个经典的题目，所以就直接翻阅答案去了。答案给出的提示就是用欧几里得的“辗转相除法”。当时把那个方法记了下来，只觉得太神奇了，会使用它但是一直没有理解，也不会证明它。

今年开始读研究生，选了Algorithm，相对于本科学习算法，在研究生阶段感觉很多是在复习这些内容，但也有更多的深入证明和学习。就拿gcd（Greatest Common Divisor）来说，在第0章就讲解了很多"模数"的知识和应用，在第三节课就证明了gcd的正确性。

因为gcd算法是一个经典的算法，所以在网上已经有很多关于它的证明方法和各种版本的实现方法。在此重述这些内容，只想巩固和积累一下自己所学到的知识，并方便将来的回顾。因为发现很多学过的内容在许久之后就会忘记，然后就要花很长的时间去找答案（比如大一的时候用得很熟练的求极限的各种公式，现在都想不太起来了，以致在解决问题的时候总是在怀疑做得是否正确）。

1个常识：

如果 a≥b 并且 b≤a，那么 a=b.

2个前提：

1）只在非负整数范围内讨论两个数 m 和 n 的最大公约数，即 m, n ∈ N.

2）0可以被任何数整除，但是0不能整除任何数，即 ∀x(x|0) and ∀x(0| x).

1个引理：

假设 k|a, k|b，则对任意的 x,y ∈ Z， k|(xa+yb)均成立.

证明：

k|a => a=pk, k|b => b==qk (其中 p,q ∈ Z)

于是有 xa+yb=xpk+yqk=(xp+yq)k

因为 k|(xp+yq)k, 所以 k|(xa+yb)

gcd的Euclid算法证明：

命题：对任意 m, n ∈ N，证明gcd(m,n) = gcd(n, mmodn)

证明：

令 k=gcd(m,n),则 k|m 并且 k|n;

令 j=gcd(n, mmodn), 则j|n 并且 j|(mmodn);

对于m, 可以用n 表示为 m=pn+(mmodn);

由引理可知 j|m（其中 x=p,y=1）, 又 j|n，于是 j 是 m 和 n 的公约数（但不一定是最大的）;

因为 k 是 m 和 n 的最大公约数，所以必有 k≥j;

通过另一种表示形式：(mmodn)=m-pn,同理可得：

k|(mmodn),又k|n，于是 k 是 (mmodn) 和 n 的公约数（也不一定是最大的）;

同样由 j 是 n 和 (mmodn) 的最大公约数可以得到 j≥k;

由常识，得出结论 k=j,

即gcd(m,n) = gcd(n, mmodn) ，得证。

gcd算法的C语言实现：

//递归版本 int gcd(int m, int n) { 	return n? gcd(n,m%n) : m; } //无递归版本 int gcd(int m, int n) { 	while (n) 	{  n = m^n;  m = m^n;  n = (m^n)%m; 	}  return m; } //当m=0,n=0时， gcd(m,n)返回0， 我们可以视其为无穷大 （见评论）

其他：

gcd除了是“最大公约数（Greatest Common Divisor）”之外，还有什么意思？

在上完这一章算法课的很长时间里，我看到gcd的第一反应永远都是“最大公约数”，但是如果把它当作是拼音的缩写的话，我们会看到它也就是我们敬爱的party。而且两者之间还有很大的联系：

如果 k=gcd(m,n)并且 m>0,n>0，则可以知道 k≤m 并且k≤n，（当有一个数为0，比如n=0，那么 k=gcd(m,n)=m≥0=n）。即在m和n都是正整数的条件下，通过gcd运算（我们姑且把它看作是一个运算符吧）得到的结果一定不会大于原来的任意一个数字。

而k=gcd(m,n)这一小段代码中，我可能犯了一个编程大计：代码没有可读性，变量名无法指示变量的含义和作用（但是本来就只是两个普通的数字，真想不出什么比较合适的变量名）。总之我们就给它们一个更好的名称吧：

speech=gcd(myWords，policyOfParty);

啥意思？就是说，我们最终讲出来的话（speech）的内容和含义，不会高于我们原本的意思（myWords），但也永远不能高于policyOfParty。

当然这也是有例外的，比如当policyOfParty=0的时候，就有了speech=myWords。这大概就是言论自由的状态吧。

不过活在世上，说话总是要有个度，因此也不是说什么好或什么不好，就比如，我再把代码改改也是一样的：

action=gcd(behavior，moral);//行为不能超过道德

joke=gcd(words，mentalCapacityOfOthers);//玩笑不能超过别人的心理承受能力

....

哈哈，程序真有意思，总是能反应出现实的百态。

三 : 灵感编程：最大公约数算法解析

给定两个正整数，求其最大公约数，相信这是每一个写代码的同学绝壁遇见过的练习，当然解法也非常多，下面先给出一个没有经过任何算法处理的程序：

publicstaticintgetResult(inta,intb){ 
intmax=(a>b)?a:b; 
intresult=0; 
for(inti=1;i<max;i++){ 
if(a%i==0&&b%i==0){ 
result=i; 
} 
} 
returnresult; 
}

这样当然是可以解出来的，但是要循环遍历其中较大的正整数，如果两个数量都非常大的话，效率是非常低的，每当遇到效率低下的程序，我们必然会想到优化，算法优化总是很靠谱的一种方法。下面就列出几种添加算法的方法来解决最大公约数的问题。

解法一：

辗转相除法，假设求正整数 num1,num2 的最大公约数，假设f(x,y)为两者的最大公约数,取 k = x / y (取整)，b = x % y (取余)；则 x = k y + b ;那么能同时被x ，y整除的数必然也同时能被 b , y 整除，能被b ， y整除的数也能同时被x，y整除，也就是说，x，y的最大公约数就是b，y的最大公约数，则有 f (x , y) = f(y , x%y) (x>=y>0),这样递归运算，比如

f(42,30) = f(30,12) = f(12 , 6) = f(6,0) = 6; 这样将运算次数直接降低了很多。下面附上代码：

intresult=((y==0)?x:gcd(y,x%y)); 
returnresult; 
}

解法二：

解法一虽然很好的解决了求公约数的问题，但是算法中包含有除法，在计算机中除法的开销是很大的，能不能不用除法呢。可以这样考虑，一个数能被x , y整出，必然也能被x-y，y整出，也就是一个数被x，y整出是这个数被x-y，y整出的充分必要条件。那么f(x, y) = f(x-y , y);这样计算的话，就可以把大整数之间的取模运算转换为大整数之间的减法运算。由于f（x，y）= f（y，x），为了避免求出一个正数和一个负数的最大公约数，要灵活运用f（x，y）= f（y，x）,迭代进行，直到一方为0；比如：

f(42,30) = f(30,12) = f(18 , 12)= f(12 , 6) = f(6,6)= f(6 , 0) = 6;这样运算跟上面的方法比起来，优化了大数据取模的问题，但是运算次数会增大，代码如下：

private static int gcd(int x, int y) {

if(y==0){ 
returnx; 
} 
if(x<y){ 
returngcd(y,x); 
}else{ 
returngcd(x-y,y); 
} 
}

解法三：

解法一的不足之处在于复杂的大数据除法运算，解法二虽然干掉了大数据的除法运算，但是增加了操作次数。两种方法都不是非常的完美，那么我们就用第三种方法来解决，第三种方法使用的二进制方案，估计很多同学看到01100100就要放弃了，千万不要，其实这东西不难。

对于x，y来说，有x=k * x1,y = k * y1 ,则f(x ,y) = f(k * x1,k * y1) = k * f(x1 ,y1);此为一。

另外，如果 x = p * x1,且p为素数，y%p != 0,则f（x ，y）= f(p * x1, y) = f(x1 ,y);此为二。

由一和二两个公式，我们可以计算公约数了：

设p=2：

假设x，y都是偶数：f（x，y）= 2f(x»1,y»1);

假设x是偶数，y是奇数：f(x,y) = f(x»1,y);

假设x是奇数，y是偶数：f(x,y) = f(x,y»1);

假设x，y都是奇数：f(x,y) = f(y,x-y);—这是根据解法二中推出来的

下面还以42 和 30 为例：

f(42,30) = f(101010,11110) = 2f(10101,1111) = 2f(1111,110)=2 * f(1111,11) = 2 f (1100,11) = 2f(110,11)=2 f(11,11) = 2 f(0,11) = 2 3=6

括号中均为二进制表达，这样最坏的情况下，复杂度也就是log 2(max(x,y));—-2是底数，尼玛，这格式弄不出来。

下面附上代码：

if(x<y){ 
returngcd(y,x); 
} 
if(y==0){ 
returnx; 
} 
if(isEven(x)){ 
if(isEven(y)){ 
//x，y都为偶数，f(x,y)=2*f(x/2,y/2)
returngcd(x>>1,y>>1)<<1; 
}else{ 
//x偶数,y奇数，f(x,y)=f(x/2,y)
returngcd(x>>1,y); 
} 
}else{ 
if(isEven(y)){ 
//x奇数，y偶数，f(x,y)=2*f(x,y/2)
returngcd(x,y>>1); 
}else{ 
//x，y都为奇数，f(x,y)=f(x-y,y)
returngcd(x-y,y); 
} 
} 
} 
publicstaticbooleanisEven(intx){ 
return(x%2==0)?true:false; 
}

以前根本没有想过这么些玩意，第一次看算法，顿时感觉高大上啊，不过的确，看到这样解决以前常用来解决的公约数问题，的确眼前一亮啊，希望大家多多给意见哦~

原文链接：http://my.oschina.net/u/858241/blog/209774

四 : 最大公约数

教学目标

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．分析：质数和互质数有什么不同？

（意义不同，质数是对一个数说的，互质数是对两个数的关系说的．）

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．教学求的一般书写格式．

启发：为了简便能不能边分解质因数边找公有的质因数？

（把两个短除式合并）

18和30的是2×3＝6

5．反馈练习：求12和20的．

6．小结求两个数的的方法．

①学生讨论．

②师生归纳：求两个数的，一般先用这两个数公有的质因数去除，一直除到所得的商是互质数为止，然后把所有的除数乘起来．

③教师说明：做短除法时，除数通常是这两个数公有的质因数，并从最小的开始除起；也可以用一个合数去除，只要能够整除这两个数就行．

④反馈练习：求36和54的．

三、全课小结．

今天这节课我们主要研究了用什么方法求两个数的及相应概念，（板书：）它是为以后学习约分做准备的，希望同学们知道知识间是有必然联系的．

四、随堂练习．【演示课件“练习”】

1．填空．

（1）（）叫做这几个数的公约数，其中（）叫做这几个数的．

（2）（）叫做互质数．

（3）求两个数的，一般先用这两个数（）连续去除，一直除到所得的商是（）为止，然后把（）连乘起来．

2．先把下面的两个数分解质因数，再求出它们的．

12＝（）×（）×（）

30＝（）×（）×（）

12和30的是（）×（）＝（）

3．判断．

（1）3和5是互质数．（）

（2）6和8是互质数．（）

（3）1和6是互质数．（）

（4）1和44不是互质数．（）

（5）14和15不是互质数．（）

五、布置作业．

求下面每组数的．

6和9 16和12 42和54 30和45

六、板书设计

五 : 最大公约数

教学目标