最大公约数和最小公倍数

用两种方法实现的求两个数的最大公约数和最小公倍数方法。留着为以后参考。

文件:	最大公约数和最小公倍数.rar
大小:	0KB
下载:	下载

一种方法是采用辗转相除法，另一种就是采用累除法。

/*//辗转相除法
int main(int argc, char* argv[])
{
 int p,r,n,m,temp;

 printf("请输入两个正整数n,m：");
 scanf("%d,%d",&n,&m);
 if (n    {
  temp=n;
  n=m;
  m=temp;            //把大数放在n中，小数放在m中
    }

 p=n*m;                   //先将m和n的乘积保存在p中，以便求最小公倍数时用

 while (m!=0)               //求m和n的最大公约数
    { r=n%m;
     n=m;
     m=r;
    }
 printf("它们的最大公约数为：%d\n",n);
 printf("它们的最小公倍数为：%d\n",p/n);    //p是原来两个整数的乘积

 return 0;
}
*/

 

//累除法

int main(int argc, char* argv[])
{
 int n,m,temp;
 int a,b; //最大公约数a,最小公倍数b

 printf("请输入两个正整数n,m：");
 scanf("%d,%d",&n,&m);
 if (n>m) //m=max(m,n)
    {
  temp=n;
  n=m;
  m=temp;           
    }
 if(m%n==0) a=n;
 else{
  for(int i=1;i<=n;i++)
  {
   if(m%i==0&&n%i==0)
   {
    a=i;
    printf("a=%d\n",a);
   }
  }
 }
 printf("最大公约数:%d\n",a);

 b=m*n/a;
 printf("最小公倍数:%d\n",b);

 return 0;
}