c语言求最大公约数、最小公倍数
最大公约数、最小公倍数
穷举法求最大公约数、最小公倍数
#include <stdio.h>
int main()//穷举法求最大公约数最小公倍数
{int a,b,n,t;
printf("请输入正整数a，b，用逗号隔开：");
scanf("%d,%d",&a,&b);
for(n=a;;n--)
if(a%n==0&&b%n==0)
{printf("%d和%d的最大公约数是：%d\n",a,b,n);
break;
}
for(n=b;;n++)
if(n%a==0&&n%b==0)
{printf("%d和%d的最小公倍数是：%d\n",a,b,n);
break;
}
return 0;
}
/*第一个for循环 n初值为b也可以（只是循环次数会变多或变少）
第二个for循环 n初值为a也可以*/
另一种写法：
#include <stdio.h>
int main()
{
int a,b,i;
printf("请输入正整数a，b，用逗号隔开：");
scanf("%d,%d",&a,&b);
for(i=a<b?a:b;a%i!=0||b%i!=0;--i)/*两个数的最大公约数总是<=小的一个数，所以是i=a<b?a:b; 某数%i!=0说明i不是某数的约数，即a%i!=0和b%i!=0只要有一个成立就退出穷举*/
;//空循环体
printf("最大公约数是%d\n",i);
return 0;
}
大数翻倍法求最小公倍数，“小数打折法”求最大公约数
#include <stdio.h>//大数翻倍法求最小公倍数，“小数打折法”求最大公约数
int main(){
int a,b,a1,b1,r,i,t;
printf("请输入两个正整数\n");
scanf("%d,%d",&a,&b);
a1=a;b1=b;
if(a>b)
{t=a;a=b;b=t;}
r=b;i=2;
while(1)
{
if(r%a==0) break;
else r=b*i++;//大数翻倍法求最小公倍数
}
printf("%d和%d的最小公倍数是%d\n",a1,b1,r);
r=a;i=2;
while(1)
{
if(b%r==0) break;
else
{r=a%i?r:a/i;//“小数打折法”求最大公约数
i++;
}
}
printf("%d和%d的最大公约数是%d\n",a1,b1,r);
printf("\n");
return 0;
}
辗转相除法求最大公约数，公式求最小公倍数
【辗转相除法程序一】
/*由于事先不知道辗转相除多少次，即事先不知道循环次数，因此，循环结构用while语句实现。*/
程序代码：
#include <stdio.h>
int main()
{int a,b,a1,b1,r;
printf("请输入正整数a，b：");
scanf("%d,%d",&a,&b);
if(a==0||b==0)
printf("输入参数错\n");
else
{a1=a,b1=b;//保存a,b
while(r=a%b)//辗转相除
{a=b;
b=r;
}
printf("%d和%d的最大公约数是：%d\n",a1,b1,b);
printf("%d和%d的最小公倍数是：%d\n",a1,b1,a1*b1/b);
}
return 0;
}
说明：求最大公约数的算法描述如下：
①a除以b得余数r;若r=0，则b为所求的最大公约数。
②若r≠0，以b为a，r为b，继续①
上述辗转相除过程中余数逐步变小，相除过程总会结束。
此算法的实质是a和b的最大公约数等于b和b%a的最大公约数。
【辗转相除法程序二】：
#include <stdio.h>
int main()
{int m,n,r,t;
int gbs,gys;
int x,y;
printf("input two integer numbersm,n");
scanf("%d,%d",&m,&n);
if(m<n) {t=m;m=n;n=t;}
x=m;
y=n;
r=m%n;
while(r!=0)
{m=n;
n=r;
r=m%n;
}
gbs=x*y/n; //最小公倍数
gys=n; //最大公约数
printf("gbs=%d,gys=%d\n",gbs,gys);
return 0;
}
附：另一程序：
#include <stdio.h>
int main()
{int a,b,a1,b1,r;
printf("请输入正整数a，b：");
scanf("%d,%d",&a,&b);
a1=a,b1=b;
while(b!=0)//此处是b!=0不是r!=0
{r=a%b;
a=b;
b=r;
}
printf("%d和%d的最大公约数是：%d\n",a1,b1,a);//此时是a不是b
printf("%d和%d的最小公倍数是：%d\n",a1,b1,a1*b1/a);
return 0;
}
更相减损术求最大公约数
#include <stdio.h>
int main()
{int a,b,aa,bb;
printf("请输入正整数a，b，用逗号隔开：");
scanf("%d,%d",&a,&b);
aa=a;bb=b;
while(a!=b)//更相减损术
{if(a>b)
a-=b;
else
b-=a;
}
printf("%d和%d的最大公约数是：%d\n",aa,bb,a);
printf("%d和%d的最小公倍数是：%d\n",aa,bb,aa*bb/a);//公式
return 0;
}
说明：
更相减损术求最大公约数：出自《九章算术》的一种求最大公约数的算法。算法简化为：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大者减小者。继续这个操作，直到所得的减数和差相等为止。例如：
（75,24）-(51,24)-(27,24)-(3,24)-(21,3)-(18,3)-(15,3)-(12,3)-(9,3)-(6,3)-(3,3)*/
用递归方法求最大公约数
辗转相除法递归：
#include<stdio.h>//
fun1(int m,int n)//求最大公约数
{if(n==0) return m;
fun1(n,m%n);
}
int main()
{int a,b;
printf("请输入正整数a，b，用逗号隔开：");
scanf("%d,%d",&a,&b);
printf("最大公约数:%d",fun1(a,b));
return0;
}
另一种写法：
#include<stdio.h>
fun1(int m,int n)//求最大公约数
{if(m%n==0) return n;
fun1(n,m%n);
}
int main()
{int a,b;
scanf("%d,%d",&a,&b);
printf("%d",fun1(a,b));
return 0;
}
更相减损术递归：
#include <stdio.h>
int gcd(int a,int b)
{
if(a==b)
return a;
else if(a>b)
return gcd(a-b,b);
else
return gcd(a,b-a);
}
int main()
{
int a,b,c;
printf("请输入正整数a，b，用逗号隔开：");
scanf("%d,%d",&a,&b);
c=gcd(a,b);
printf("%d,%d的最大公约数＝%d\n",a,b,c);
return 0;
}
参考资料：
[1]李红卫，李秉璋.《C程序设计与训练（第三版）》.大连理工大学出版社.
[2]张彩霞，王祖凤.《计算机专业C语言 随堂练》.中国原子能出版社.