求最大公约数和最小公倍数c语言

Python019

求最大公约数和最小公倍数c语言,第1张

c语言求最大公约数和最小公倍数的方法： 求最大公约数算法： 有两整数a和b： ① a%b得余数c ② 若c=0，则b即为两数的最大公约数 ③ 若c≠0，则a=b，b=c，再回去执行① 例如求27和15的最大公约数过程为： 27÷15 余1215÷12余312÷3余0因此，3即为最大公约数。

求最小公倍数：如图所示

C语言是一门面向过程的、抽象化的通用程序设计语言，广泛应用于底层开发。C语言能以简易的方式编译、处理低级存储器。C语言是仅产生少量的机器语言以及不需要任何运行环境支持便能运行的高效率程序设计语言。

首先要知道这样的一个结论，有三个正整数a b c，若d是a b的最小公倍数，e是 d c的最小公倍数，那么e是a b c的最小公倍数。同理，我们可以推出n个数的最小公倍数的求解，而对于最小公倍数的求解过程我们可以使用一个函数LCM来求解，在此之前我们要明确最小公倍数是怎么求解的。若k是 a b的最大公约数，那么a b的最小公倍数为a*b/k。最大公约数我们可以使用辗转相除法来求得。GCD（最大公约数函数）的书写：

int GCD(int a, int b)

{

if (b == 0) return a

return GCD(b, b%a)

}

相信求解最小公倍数的函数应该能够很快的写出来，接下来就是要利用我们最开头得到的结论，这样循环遍历一次数组即可求出n个数的最小公倍数

计算最小公倍数，首先要有一个合理的算法，然后再写代码

下面给出一个辗转相除求最大公约数，再实现最小公倍数的算法实现，供参考：

#include <stdio.h>

int mcd (int a,int b) //求最大公约数

{

       int  temp 

       while(b!=0)           /*通过循环求两数的余数，直到余数为0*/

       {

               temp=a%b

               a=b              /*变量数值交换*/

               b=temp

       }

       return a            /*返回最大公约数到调用函数处*/

}

int lcm( int a, int b ) //求最小公倍数

{

       return a/mcd(a,b)*b 

}

int main()

{

       int a,b

       printf("input a b: ")

       scanf("%d %d", &a, &b )

       printf("lcm=%d\n", lcm(a,b) )

       return 0

}