C语言求最小公倍数和最大公约数四种算法(经典)

求最小公倍数的算法：

最小公倍数=两整数的乘积÷最大公约数。所以该问题可以转化为求最大公约数的算法。

求最大公约数的四种算法:

1. 辗转相除法 :

a%b得余数c
如果c = 0,则b为最大公约数
如果c不等于0,则a = b,b = c继续执行步骤1。

#include<stdio.h>
int main()   /*  辗转相除法求最大公约数 */ 
{ 
   int m, n, a, b, t, c;
   printf("Input two integer numbers:\n");
   scanf("%d%d", &a, &b);
   m=a;   n=b;
   while(b!=0)  /* 余数不为0，继续相除，直到余数为0 */ 
   { c=a%b; a=b;  b=c;}
   printf("The largest common divisor:%d\n", a);
   printf("The least common multiple:%d\n", m*n/a);
}

还有一种简写方式：

int gcd(int a,int b)
{
    if (b==0) 
        return a;
    return gcd(b, a%b);
}

2.  相减法:

若a>b，则a=a-b
若a < b，则b=b-a
若a=b，则a（或b）即为两数的最大公约数
若a≠b，则再回去执行1

#include<stdio.h>
int main ( )  /* 相减法求最大公约数 */
{  
   int m, n, a, b, c;

 printf("Input two integer numbers:\n");
   scanf ("%d,%d", &a, &b);
m=a; n=b; 
     /* a, b不相等，大数减小数，直到相等为止。*/ 

   while ( a!=b) 
         if (a>b)  a=a-b;

         else  b=b-a;

   printf("The largest common divisor:%d\n", a);
   printf("The least common multiple:%d\n", m*n/a);
}

4.枚举法：
已知1是一个公约数，但是1不是最大公约数，所以可以检测K=2,3,4…..是否为n1和n2的公约数，直到k大于n1或者n2。将公约数存储在gcd的变量中,gcd初值设为1

int gcd = 1;
for(int k = 2;k <= n1&&k <= n2;k++){
    if(n1 % k == 0&& n2 % k == 0)
        gcd = k;
}

C语言求最小公倍数和最大公约数四种算法(经典)

求最小公倍数的算法：

求最大公约数的四种算法:

推荐阅读