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

Python022

求最大公约数和最小公倍数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语言是仅产生少量的机器语言以及不需要任何运行环境支持便能运行的高效率程序设计语言。

c语言求最大公约数和最小公倍数，回答如下：

在做C语言相关练习的时候，会遇见比较经典的一道题型，就是求最大公约数或者最小公倍数。那么先普及一下什么是最大公约数和最大公倍数：

最大公约数：指能够整除多个整数的最大正整数。例如8和12的最大公约数为4。

最小公倍数：两个或多个整数最小的公共倍数。例如6和24的最小公倍数为24。

1.暴力求解

以求最大公约数为例，若求 a b 的最大公约数，所求的数最大不会超过两个数中较小的数。那可以从这个较小的数开始被a b同时试除，如果试除的余数为0，那么该数即为所求。如果不满足余数同时为零的条件，那么该数减一，接着试除，直到满足余数同时为零的条件为止。

2.辗转相除法

辗转相除法是用来求最大公约数的，同时最小公倍数满足这样一条数学性质：两数之积除以最大公约数即为最小公倍数.所以用辗转相除法是可以间接求最小公倍数的。

辗转相除法的大概思路：用两数相除，如果余数为零即为所求，如果余数不为零，上一轮相除所得的余数为除数，同时上一轮的除数现在成为被除数，直到余数为零不再相除，此时的除数即为所求。

//求两个数的最大公约数和最小公倍数的函数

void fun(int a,int b)

{

    int temp,r

    int v

      

    if(a<b)

    {temp=a a=b b=temp}    //将大数放在a中,小数放在b

    v=a*b

    r=a%b

    while(r!=0)

    {

        a=b

        b=r

        r=a%b

    }

    v/=b

    printf("最大公约数为%d\n",b)

    printf("最小公倍数为%d\n",v)

}