C语言求最大公约数和最小公倍数算法总结
温柔似野鬼°
928次浏览
2021年01月28日 15:46
最佳经验
本文由作者推荐
教师个人进修计划-怎么开通黄钻
C
语言求最大公约数和最小公倍数算法总结
单位：山东科技大学
作者：左键
摘
< br>要：介绍自己通过学习使用
C
语言求任意两个数的最大公约数和最小公倍数的基本算法思 想、
算法过程、代码实现以及分析比较。
关键词：
C
语言
算法
最大公约数
最小公倍数
中图分类号：
TP312
文献标识码：
A
The
algorithm
summarization
of
evaluating
the
greatest common divisor and the least common
multiple in C Language
Abstract
：
Introduction to the algorithm basic thought, algorithm process and code realization and its
analysing
comparison
in
terms
of
evaluating
the
greatest
common
divisor
and
the
least
common
multiple of any two positive integers by learning to using C Language
Keywords
：
C
Language
algorithm
the greatest common divisor
the least common multiple
C
语言求最大公约数和最小公倍数可以说是
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
的值给
b
；
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();