[编程入门]最大公约数与最小公倍数（三种方法）

解题思路:

注意事项:

参考代码:

 方法一：

#include <stdio.h>

/*

输入两个正整数m和n，求其最大公约数和最小公倍数。

*/

int m1011(){

int m,n;

int mm=0,ss=0,t1,t2;

scanf("%d %d",&m,&n);

if(m%n==0){

mm=n;

ss=m;

}

else if(n%m==0){

mm=m;

ss=n;

}

else{

t1=(m<n)?m:n;

t2=(m>n)?m:n;

for(int i=t1/2;i>0;i--){

if(m%i==0 && n%i==0)

{

mm=i;

break;

}

}

for(int i=2;i<t2;i++){

if(t2*i%t1==0){

ss=t2*i;

break;

}

}

}

printf("%d %d\n",mm,ss);

return 0;

}

方法二：

/*

短除法：

12/1=12 18/1=18 ......1

12/2=6 18/2=9 ......2

6/3=2 9/3=3 ......3

最大公约数：1*2*3=6

最小公倍数：2*3*1*2*3=36 

*/

int m1011_2(){

int m,n,mm,ss;

int gcd=1;//最大公约数 

scanf("%d %d",&m,&n);

mm=m>n?m:n;

ss=m<n?m:n;

if(mm%ss==0){

printf("%d %d",ss,mm);

}

else

{

for(int i=ss/2;i>0;i--){

if(m%i==0 && n%i==0){

m/=i;

n/=i;

gcd*=i;

}

}

printf("%d %d",gcd,m*n*gcd);

} 

return 0;

} 

方法三：

/*

辗转相除法（欧几里得算法）：

例1：

18/12=1 ......6

12/6=2 ......0

最大公约数：6

最小公倍数：18*12/6=36

例2：

9/6=1 ......3

6/3=2 ......0

最大公约数：3

最小公倍数：9*6/3=18

例3：

7/5=1 ......2

5/2=2 ......1

2/1=0 ......0

最大公约数：1

最小公倍数：7*5/1=35

例4:

90/15=6 ......0

最大公约数：15

最小公倍数：90*15/15=90 

*/

int Gcd(int m,int n){

return (m%n==0)?n:Gcd(n,m%n);

}

int m1011_3(){

int m,n;

int gcd=1;

scanf("%d %d",&m,&n);

//gcd=Gcd(m>n?m:n,m<n?m:n);

gcd=Gcd(m,n);

printf("%d %d",gcd,m*n/gcd);

return 0;

}