C语言求最大公约数和最小公倍数算法
巡山小妖精
661次浏览
2021年02月01日 07:58
最佳经验
本文由作者推荐
四海为家的意思-听儿歌
C
语言求最大公约数和最小公倍数算法
C
语言求最大公 约数和最小公倍数可以说是
C
语言编程学习中一个重点和难点，它常常作为计
算机专业 学生参加各种考试必须要把握的内容。其算法方面除常用的辗转相除法外、还可以根据数
学定义法、递归 调用法等。下面结合我学习以来的笔记整理、总结几种常用的方法进行比较，以便
能够更好的理解、应用 、共勉。
前提：假设求任意两个整数的最大公约数和最小公倍数，采用函数调用形式进行。
1
、辗转相除法
辗转相除法（又名欧几里德法）
C
语言中 用于计算两个正整数
a,b
的最大公约数和最小公倍数，
实质它依赖于下面的定理：< br>
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
/*
通过比较求出两个数中的最大值和最小值
*/
{ temp=a;a=b;b=temp;}
/*
设置中间变量进行两数交换
*/
while(b!=0)
/*
通过循环求两数的余数，直到余数为
0*/
{
temp=a%b;
a=b;
/*
变量数值交换
*/
b=temp;
}
return (a);
/*
返回最大公约数到调用函数处
*/
}
int multiple (int a,int b)
/*
自定义函数求两数的最小公倍数
*/
{
int divisor (int a,int b);
/*
自定义函数返回值类型
*/
int temp;
temp=divisor(a,b);
/*
再次调用自定义函数，求出最大公约数
*/
return
(a*b/temp);
/*
返回最小公倍数到主调函数处进行输出
*/
}
#include
/*
输入输出类头文件
*/
main()
{
int m,n,t1,t2;
/*
定义整型变量
*/
printf(
*
提示输入两个整数
*/
scanf(
/*
通过终端输入两个数
*/
t1=divisor(m,n);
/*
自定义主调函数
*/
t2=multiple(m,n);
/*
自定义主调函数
*/
printf(
higest
common divisor is %dn
/
*
输出最大公约数
*/
printf(
t2
);
/*
输出最小公倍数
*/
}
启示：请注意算法中变量数 值之间的相互交换方法、如何取模、怎样进行自定义函数及主调函
数与被调函数间的相互关系，函数参数 的定义及对应关系特点，利用控制语句如何实现
。
②、函数递归调用
int gcd (int a,int b)
{ if(a%b==0)
return b;
else
return gcd(b,a%b);
}
#include
main()
{
int m,n,t1;
printf(
scanf(
t1=gcd(m,n);
printf(
/*
最大公约数
*/
printf(
/*
最小公倍数
*/
getch();
}
启示：采用递归调用法要注意递归终止条件的描述，只有找到递归变化的规律，才能有效地 解
决问题。
2
、穷举法（利用数学定义）
穷举法（也叫 枚举法）穷举法求两个正整数的最大公约数的解题步骤：从两个数中较小数开始
由大到小列举，直到找到 公约数立即中断列举，得到的公约数便是最大公约数
。
①、定义
1
：
对两个正整数
a,b
如果能在区间
[a,0]
或
[b,0]
内能找到一个整数
temp
能同时被
a
和
b< br>所整除，则
temp
即为最大公约数。