用C++找出HCF和LCF

最大公约数Highest Common Factor(HCF)
最小公倍数Lowest Common Factor(LCF)


这里介绍了2种找出HCF的方法
只要找到了HCF，使用以下算法就可找出LCF

LCF=两整数的乘积 / HCF


1. 辗转相除法

有两整数a和b：
① a%b得余数c
② 若c=0，则b即为两数的最大公约数
③ 若c≠0，则a=b，b=c，再回去执行①

例如求27和15的最大公约数过程为
27÷15 余12
15÷12余3
12÷3余0
因此，3即为最大公约数

Code:

int func(int max,int min)   //if max = 30,min = 20
{
   int temp = 0;
   if(max < min)
   //make sure max is really max
   {
      temp = max;
      max=min;
      min=temp;
   }

   do
   {
      temp = max % min;   //reuse temp variable   //30%20   = 10   //20%10 = 0
      max = min;   //max = 20   //max = 10
      min = temp;  //min = 10   //min = 0
   }while(min != 0);

   return max;   //10
}

Code:

//递归版本
int cal_HCF(int max,int min)
{
   int temp = 0;
   if(max < min)   //make sure max is really max
   {
      temp = max ;
      max = min;
      min = temp;
   }

   temp = max % min;   //reuse temp
   max = min;
   min = temp;

   if(min != 0)
      cal_HCF(max,min);
   else
      return max;

}


2.相减法

有两整数a和b
① 若a>b，则a=a-b
② 若a小于b，则b=b-a
③ 若a=b，则a（或b）即为两数的最大公约数
④ 若a≠b，则再回去执行①

例如求27和15的最大公约数过程为：
27－15＝12
( 15>12 ) 15－12＝3
( 12>3 )12－3＝9
( 9>3 ) 9－3＝6
( 6>3 )6－3＝3
( 3==3 ) //answer!

Code:

void main ( )     //相减法求最大公约数
{
   int m, n, a, b, c;
   cout<<"Input two integer numbers:"<<endl;
   cin>>a;
   cin>>b;
   m=a;
   n=b;
   // a, b不相等，大数减小数，直到相等为止

   while ( a!=b)
   {
      if (a>b)        a=a-b;         
      else  b=b-a;
   }
   cout<<"The largest common divisor:"<<a<<endl;
   cout<<"The least common multiple:"<<m*n/a<<endl;
}