三种方法求公约数等

#include<stdio.h>
int main()
{
int i,j,n,p,q,tep,s,r;
scanf("%d",&n);
while(n--)
{
scanf("%d%d",&p,&q);
if(p<q)
{
tep=q;
q=p;
p=tep;
}

s=p*q;
while(q)//经过上面,q较小,最大公约数不会超过较小者
{
r=p%q;
p=q;
q=r;
}
printf("%d\t%d",q,s/q);
return 0;
}
}
printf("%d\t%d",q,s/q);
return 0;
}
}

#include<stdio.h>
#include <stdlib.h>
int gcd(int ,int);
int main()
{
int n,p,q,s,r,ss;
scanf("%d",&n);
while(n--)
{
scanf("%d %d",&p,&q);
s=p*q;
ss=gcd(p,q);

printf("%d %d\n",ss,s/ss);
}
//system("pause");
return 0;
}
/////////////////////
欧几里德算法也就是辗转相除法,有着2000年的历史了。欧几里德算法依据的算法理论是
一个定理:gcd(a,b) = gcd(b,a mod b)。
int gcd(int a,int b)
{
int temp;
if(0 == a )
{ return b; }
if( 0 == b)
{ return a; }
if(a > b)
{ temp=a; a=b; b=temp; }
int c;
for(c = a % b ; c > 0 ; c = a % b)
{ a = b; b = c; }
return b;
}
#include <stdio.h>
int a(int x,int y)
{
if(x%y==0)
return y;
else
return a(y,x%y);
}
int b(int x,int y)
{
return x*y/a(x,y);
}
int main()
{
int m,n,t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&m,&n);
printf("%d %d\n",a(m,n),b(m,n));
}
return 0;
}

上一篇:安装kubectl


下一篇:2019 .NET China Conf:路一直都在,社区会更好