如何求两数的最大公约数
一：更相减损
//熟知的辗转相除法变形
main()
{
int a,b;
scanf("%d %d",&a,&b);
while(a!=b)
{
if(a>b)
a-=b;
else
b-=a;
}
printf("%d",a);
}
二：
辗转相除
//一般用递归描述算法
gcd(m,n)与gcd(n,m mod n)相同 为什么？
gcd(m,0)=m 为什么？
两数不需比较大小也行 为什么 ？
main()
{
int a,b,r,t;
scanf("%d %d",&a,&b);
if(a<b)
{
t=a;
a=b;
b=t;
}
do
{
r=a%b;
a=b;
b=r;
}while(r!=0);
printf("%d",a);
}
三：
连续整数检测
//根据最大公约数的定义来的
main()
{
int a,b,t;
scanf("%d %d",&a,&b);
if(a<b)
t=a;
else
t=b;
while(t>=1)
{ if((a%t==0)&&(b%t==0))
break;
t--;
}
printf("%d",t);
}
四：
短除法
//
两数的公共质因数相乘 p公因数出的次数min{Pa,Pb}
int primedec(int m,int *a)//为什么这函数能求出M的所有质因数？
{
int i=0,k=2;//由最小的质数2除待分解的数
while(k<=m)
{
if(m%k==0)
{
a[i++]=k;
m=m/k;
}
else
k++;
}
}
main()
{
int a[10]={0},b[10]={0},c[10];
int m,n,i,j,k=0,s=1;
scanf("%d %d",&m,&n);
primedec(m,a);
primedec(n,b);
for(i=0;i<10;i++)
{
for(j=0;j<10;j++)
{
if(a[i]==b[j]&&b[j]!=0)
{
c[k++]=a[i];
b[j]=0;
break;
}
}
}
for(i=0;i<k;i++)
{
s*=c[i];
}
printf("%d",s);
}
程序很粗糙……
有不足的地方 还请批评指正
