从今天开始，我决心利用寒假把谭浩强的《C程序设计》（从第6章到第13章）的所有习题做一遍，发表在我的blog上。

算法思路：  可以有三种方法求两数的最大公约数。设m>n。

    1. 让k从1变到n,能同时整除m和n的最大的k即为所求。

    2. 让k从n变到1，第一个能同时整除m和n的k即为所求。

    3. 使用辗转相除法。辗转相除法的算法为：首先将 m除以 n（m>n）得余数 r，再用余数  r 去除原来的除数，得新的余数，重复此过程直到余数为 0时停止，此时的除数就是m 和 n的最大公约数。 经常使用的算法是辗转相除法。 求 m和 n的最小公倍数: m和 n的积除以 m和 n 的最大公约数。我的程序使用的是辗转相除法。由于程序比较简单，所以没有加注释。程序运行环境：Windows2000, VC++6.0。

#include

void  MaxandMin(long Num1,long Num2)
{
 long Temp=0;
 if(Num1>=Num2)     
 {
  Temp=Num2;
  while((Num1%Num2)!=0) 
  {
   Num2=Num1%Num2;
  }
  printf("最大公约数为%d\n",Num2);
  Temp=( Num1*Temp )/Num2;
  printf("最小公倍数为%d\n",Temp);
 }
 else
 {
  Temp=Num1;
  while((Num2%Num1)!=0)
  {
   Num1=Num2%Num1;
  }
  printf("两数的最大公约数为%d\n",Num1);
  Temp=( Num2*Temp )/Num1;
  printf("两数的最小公倍数为%d\n",Temp);
 }
   
}

int main()
{
 long Num1=0,Num2=0;
 printf("请输入两个整数：\n");
 scanf("%d%d",&Num1,&Num2);
 MaxandMin(Num1,Num2);
 return 1;
}

评论