最小公倍数解决思路

最小公倍数
新手求教c语言求最小公倍数算法，只要算法！！
[解决办法]
选择一个数，从1到另一个数穷举倍数，找到第一个可以整除另一个数的值，返回。代码如下：
int foo(int x, int y)
{
    for (int i = 1; i < y; i++)
        if (x * i % y == 0) return x * i;
    return x * y;
}
[解决办法]
已知m,n均为正整数，试用C语言写出求m与n的最小公倍数的算法，算法的步骤为(该算法的好处是只需用一次乘法)：
（1） 计算m*n的积，送临时变量r。
（2） 若m等于n，则输出最小公倍数r/m，算法结束。
（3） 若m大于n，计算m-n，结果送m，否则，计算n-m，结果送n。(即max = max - min)
（4） 转到（2）或者（3）。

在已知最大公约数的前提下，另一个方法：最小公倍数=m*n/最大公约数

[解决办法]
已知m,n
1. 用辗转相除法求最大公约数
2. 最小公倍数 = m*n/最大公约数
[解决办法]

引用:

n个数怎么求

比如求两个数的int foo(int x, int y) { .. }
那么如果你要求3个数就是
int foo3(int x, int y, int z)
{
    int t = foo(x, y);
    return foo(t, z);
}
如果求n个数(n >= 2)
int foon(int x[], int n)
{
    int t = foo(x[0], x[1]);
    for (int i = 2; i < n; i++)
        t = foo(t, x[i]);
    return t;
}
[解决办法]
最大公倍数就是两数相乘再除以最大公约数，比如12、8，最大公约数是4，那么他们最小公倍数就是28*8/4=24。

最大公约数用碾转相除法，大的数除以小的数，如果能整除，则为小的那个数，如果不能，则以小的那个数为大数，余数为小的数，继续作此运算。

最好用循环，递归效率低些。


//a>b
int GetGCD(int a, int b)
{
    int remainder = a % b;
    while(remainder > 0)
    {
        a = b;
        b = remainder;
        remainder = a % b;
    }

    return b;
}
[解决办法]
比如x,y,z的最小公倍数，先求其中两个的最小公倍数，比如x,y最小公倍数得到是m,再求m,z的最小公倍数。n个数也是一样的道理。

引用:

已知m,n
1. 用辗转相除法求最大公约数
2. 最小公倍数 = m*n/最大公约数

[解决办法]
比如x,y,z的最小公倍数，先求其中两个的最小公倍数，比如x,y最小公倍数得到是m,再求m,z的最小公倍数。n个数也是一样的道理。

引用:

n个数怎么求

[解决办法]

#include<stdio.h>

int lcm(int,int);

int main(){

   

    int a,b,l;

    printf("Enter any two positive integers ");
    scanf("%d%d",&a,&b);
 
    if(a>b)
         l = lcm(a,b);
    else
         l = lcm(b,a);
   
    printf("LCM of two integers is %d",l);

    return 0;
}

int lcm(int a,int b){
  
    int temp = a;

    while(1){
         if(temp % b == 0 && temp % a == 0)
             break;
         temp++;
    }

   return temp;
}

[解决办法]
#include <stdio.h>
int gcd(int v1,int v2)
{
while(v2) {
int temp = v2;
v2 = v1 % v2;
v1 = temp;
}
return v1;
}
int main()
{
          int a,b,n;

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

}

查看更多 下一篇