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

THE END
最后修改:2020 年 01 月 16 日 20 : 55
本文链接:https://www.j000e.com/C/CGreatestCommonDivisorandMultiple.html
版权声明:本文『[C]求N个数的最大公约数与最小公倍数』为『Joe』原创。著作权归作者所有。
转载说明:[C]求N个数的最大公约数与最小公倍数 || Joe's Blog』转载许可类型见文末右下角标识。允许规范转载时,转载文章需注明原文出处及地址。
Last modification:January 16, 2020
If you think my article is useful to you, please feel free to appreciate