1、两个数的最小公倍数=两个数的乘积÷两个数的最大公约数
2、用辗转相除法求两个数的最大公约数：

 319÷377余319；

 377÷319余58；

 319÷58余29；

 58÷29余0；

 故319和377的最大公约数是29；319和377的最小公倍数是319*377÷29=4147；

如下:

#include <stdio.h>
#include <stdlib.h>
int mincommon(int a,int b)
{
    //先用辗转相除法求最大公约数,再求最小公倍数
    int c=a*b,remainder;//remainder余数
    while(1)
    {
        remainder=a%b;
        if(remainder==0) return c/b;//最小公倍数=两数乘积÷最大公约数
        a=b;
        b=remainder;
    }
}
/*
若只求最大公约数
int GCD(int a,int b)//GCD greatest common divisor 最大公倍数
{
    int remainder;
    while(1)
    {
        rem=a%b;
        if(rem==0) return b;
        a=b;
        b=rem;
    }
}
*/
int main()
{
    int n,i;//要输入n个数
    while(scanf("%d",&n)!=EOF)
    {
        int a[n+1];
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        int ans=a[1];
        for(i=1;i<=n;i++)
        {
            ans=mincommon(ans,a[i]);
        }
        printf("%d\n",ans);
    }
    return 0;
}

参考了:
https://blog.csdn.net/gunianshan/article/details/82025992

• • -

    版权声明:本文为原创文章,版权归Joe所有,转载请注明出处.

    本文链接:https://www.j000e.com/C/CGreatestCommonDivisorandMultiple.html
    
    本作品采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。