在做C语言相关练习的时候,会遇见比较经典的一道题型,就是求最大公约数或者最小公倍数。那么先普及一下什么是最大公约数和最大公倍数:
最大公约数:指能够整除多个整数的最大正整数。例如8和12的最大公约数为4。
最小公倍数:两个或多个整数最小的公共倍数。例如6和24的最小公倍数为24。
1.暴力求解
以求最大公约数为例,若求 a b 的最大公约数,所求的数最大不会超过两个数中较小的数。那可以从这个较小的数开始被a b同时试除,如果试除的余数为0,那么该数即为所求。如果不满足余数同时为零的条件,那么该数减一,接着试除,直到满足余数同时为零的条件为止。
2.辗转相除法
辗转相除法是用来求最大公约数的,同时最小公倍数满足这样一条数学性质:两数之积除以最大公约数即为最小公倍数.所以用辗转相除法是可以间接求最小公倍数的。
辗转相除法的大概思路:用两数相除,如果余数为零即为所求,如果余数不为零,上一轮相除所得的余数为除数,同时上一轮的除数现在成为被除数,直到余数为零不再相除,此时的除数即为所求。
c语言最大公约数最小公倍数如下:
从键盘输入两个正整数a和b,求其最大公约数和最小公倍数。
算法思想:利用格式输入语句将输入的两个数分别赋给a和b,然后判断a和b的关系,如果a小于b,则利用中间变量t将其互换。再利用辗转相除法求出最大公约数,进而求出最小公倍数。最后用格式输出语句将其输出。
程序代码
调试运行结果:当输入的两个数为15和65时,打印出的结果如下所示:
当输入的两个数为16和72时,打印出的结果如下所示:
总结:实例中用到了辗转相除法来求最大公约数。在求最小公倍数时要清楚最大公约数和最小公倍数的关系,即两数相乘的积除以这两个数的最大公约数就是最小公倍数。
C语言是一门面向过程的、抽象化的通用程序设计语言,广泛应用于底层开发。C语言能以简易的方式编译、处理低级存储器。C语言是仅产生少量的机器语言以及不需要任何运行环境支持便能运行的高效率程序设计语言。
尽管C语言提供了许多低级处理的功能,但仍然保持着跨平台的特性,以一个标准规格写出的C语言程序可在包括类似嵌入式处理器以及超级计算机等作业平台的许多计算机平台上进行编译。
#include <stdio.h>
long long int gongyue(long long int m,long long int n){
long long int c
if(m<2 || n<2) return 44
if(m>n){
c=m%n
while(c>0){
m=n
n=c
c=m % n
}
}
else{
c=n % m
while(c>0){
n=m
m=c
c=n % m
}
}
m=n
return m
}
long long int gongbei(long long int m,long long int n){
return m/gongyue(m,n)*n
}
int main(){
long long int a,b,c,m,n
printf("请输两个正整数a,b:")
scanf("%lld%lld",&a,&b)
m=gongyue(a,b)
n=gongbei(a,b)
printf("最大公约数%lld,最小公倍数%lld\n",m,n)
return 0
}