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

1、C 语言求最大公约数和最小公倍数算法总结 单位：隆回县职业中等专业学校 作者：刘小华 摘 要：介绍自己通过学习使用 C 语言求任意两个数的最大公约数和最小公倍数的基本算法思想、 算法过程、代码实现以及分析比较。关键词： C 语言算法 最大公约数 最小公倍数中图分类号： TP312 文献标识码： AThe algorithm summarization of evaluating the highest common divisor and the lowest common multiple in C LanguageZhao Ye Lin Tutor Teacher： Liu Xiao Hu

2、aAbstract ： Introduction to the algorithm basic thought, algorithm process and code realization and its analysing comparison in terms of evaluating the highest common divisor and the lowest common multiple of any two positive integers by learning to using C LanguageKeywords ： C Language algorithm th

3、e highest common divisor the lowest common multipleC 语言求最大公约数和最小公倍数可以说是 C 语言编程学习中一个重点和难点，它常常作为计 算机专业学生参加各种考试必须要把握的内容。其算法方面除常用的辗转相除法外、还可以根据数 学定义法、递归调用法等。下面结合我学习以来的笔记整理、总结几种常用的方法进行比较，以便 能够更好的理解、应用、共勉。前提：假设求任意两个整数的最大公约数和最小公倍数，采用函数调用形式进行。1、辗转相除法辗转相除法(又名欧几里德法) C 语言中用于计算两个正整数 a,b 的最大公约数和最小公倍数， 实质它依赖于下面的定理

4、：ab=0gcd(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)/* 自定义函数求两数的最大公约数 */* 定义整型变量 */if(ab)

5、?b:a; /* 采种条件运算表达式求出两个数中的最小值 */ while(temp0)if (a%temp=0&b%temp=0) /* 只要找到一个数能同时被 a,b 所整除，则中止循环 */ break;temp-;/* 如不满足 if 条件则变量自减，直到能被 a,b 所整除 */return (temp); /* 返回满足条件的数到主调函数处 */#include stdio.hmain()int m,n,t1;printf(please input two integer number:);scanf(%d%d,&m,&n);t1=divisor(m,n);printf(The h

6、igest common divisor is %dn,t1);getch();、定义 2： 对两个正整数 a,b, 如果若干个 a 之和或 b 之和能被 b 所整除或能被 a 所整除，则 该和数即为所求的最小公倍数。代码为：int multiple (int a,int b)int p,q,temp;p=(ab)?a:b; /* 求两个数中的最大值 */q=(ab)?b:a; / * 求两个数中的最小值 */ temp=p; /* 最大值赋给 p 为变量自增作准备 */ while(1) /* 利用循环语句来求满足条件的数值 */ if(p%q=0)break;/* 只要找到变量的和数能被

7、a 或 b 所整除，则中止循环 */p+=temp;/* 如果条件不满足则变量自身相加 */return (p);#include stdio.hmain()int m,n,t2;printf(please input two integer number:);scanf(%d%d,&m,&n);t2=multiple(m,n);printf(The least common multiple is %dn,t2);getch(); 启示：根据数学定义求任意两个正整数的最大公约数和最小公倍数，相对辗转相除法来说，易 懂，容易被学习者接受，但也请读者注意强制退出循环过程的条件、变量的特点及控制语句的使用。结束语结束语C 语言编程关键在于确定好算法及算法过程，同时要合理定义变量和函数及控制语句操作，只 有这样才能保证编程的正确性、 、可读性、实用性。参考文献1 C 程序设计 第二版 谭