YTU 1047:C语言习题5.9–求两个整数的最大公约数和最小公倍数

http://202.194.119.110/contest.php?cid=1047
Time Limit:1 Sec Memory Limit:128MB

题目描述

写两个函数,分别求两个整数的最大公约数和最小公倍数,用主函数调用这两个函数,并输出结果两个整数由键盘输入。

输入

两个数

输出

最大公约数 最小公倍数

样例输入

6 15

样例输出

3 30

提示

主函数已给定如下,提交时不需要包含下述主函数


/*  C代码   */


int main()


{


    int n,m,gys,gbs;


    int gcd(int a, int b);


    int lcm(int a, int b);


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


    gys=gcd(n,m);


    gbs=lcm(n,m);


    printf("%d %d\n",gys,gbs);


    return 0;


}


/*  C++代码   */


int main()


{


    int n,m,gys,gbs;


    int gcd(int a, int b);


    int lcm(int a, int b);


    cin>>n>>m;


    gys=gcd(n,m);


    gbs=lcm(n,m);


    cout<<gys<<" "<<gbs<<endl;


    return 0;


}

题解

公约数要用到辗转相除法(欧几里得算法),熟悉的可以直接用递归简单完成,不熟悉的可以凭借下面这张算法图一步步实现。
http://c.biancheng.net/view/507.html


至于最小公倍数,以两数中较大的一方为最小值,两数的乘积为最大值,一步步for循环暴力往上加就完事了。

#include <iostream>
using namespace std;

int gcd(int a, int b)   //gcd:greatest common divisor 最大公约数
{
//辗转相除法
  int tmp=0,bcs,cs;  //bcs 被除数 cs除数
  if(a == b){return b;}
  else{
    if(a>b){bcs=a;cs=b;} else{bcs = b;cs = a;}
    tmp = bcs%cs;
    while(tmp!=0)
    {
      bcs = cs;
      cs = tmp;
      tmp = bcs%cs;
    }
    return cs;
  }
}

int lcm(int a, int b)  //lcm:lowest common multiple 最小公倍数
{
  int max1,max2,i,result;
  if(a == b){return b;}
  else
    {
    if(a>b){max1 = a;}else{max1 = b;}
    max2 = a*b;
    for(i = max1;i <= max2;i++)
    {
      if((i%a == 0)&&(i%b == 0)){result = i;break;}
    }
      return result;
    }
}

int main()


{


    int n,m,gys,gbs;


    int gcd(int a, int b);


    int lcm(int a, int b);


    cin>>n>>m;


    gys=gcd(n,m);


    gbs=lcm(n,m);


    cout<<gys<<" "<<gbs<<endl;


    return 0;


}