请注意,本文编写于 2083 天前,最后修改于 1722 天前,其中某些信息可能已经过时。
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 国际许可协议进行许可。