哈喽C!利用輾除法求最大公約數和最小公倍數

題目：輸入兩個正整數m和n，求其最大公約數和最小公倍數。

1.程式分析：利用輾除法。

2.上代碼：

#include <stdio.h>
//程式分析：利用輾除法。
int main()
{
  int a,b,num1,num2,temp;
  printf("please input two number:\n");
  scanf("%d%d",&num1,&num2);
  if(num1<num2){
    temp = num1;
    num1 = num2;
    num2 = temp;
  }
  a = num1;
  b = num2;
  while(b!=0){   /*利用輾除法，直到b為0為止*/
    temp = a%b;
    a=b;
    b=temp;
  }
  printf("公約數:%d\n",a);
  printf("公倍數:%d\n",num1*num2/a);
}      

何為輾轉相除法？

（以下來自百度百科）

輾轉相除法， 又名歐幾裡德算法（Euclidean algorithm），是求最大公約數的一種方法。它的具體做法是：用較小數除較大數，再用出現的餘數（第一餘數）去除除數，再用出現的餘數（第二餘數）去除第一餘數，如此反複，直到最後餘數是0為止。如果是求兩個數的最大公約數，那麼最後的除數就是這兩個數的最大公約數。

結合輾除法和代碼，總結一下：

1.先比較兩個數的大小，較大者做分母，假設是b，較小者做分子，假設是a，此時會有一個餘數，假設是temp

2.用步驟1得到的餘數temp除分母b，也就是b/temp。此時會又有“第二個餘數”temp2

3.用第二餘數temp2除第一餘數temp，也就是temp/temp2

注意：以上操作是求餘數，是以用取餘%法。

4.重複步驟1，2，3，知道最後的餘數是0結束。

再來一次代碼：

#include <stdio.h>
//程式分析：利用輾除法。
int main()
{   int a,b,num1,num2,temp;
    printf("please input two number:\n");
    scanf("%d%d",&num1,&num2);
    if(num1<num2)//比較大小，大做分母，小做分子
    {   temp = num1;//這是兩個數比大小的經典算法
        num1 = num2;
        num2 = temp;
    }
    a = num1;//小者給a
    b = num2;//大者給b
    while(b!=0)/*利用輾除法，直到b為0為止*/
    {   temp = a%b;//這是重複取餘的操作
        a=b;
        b=temp;
    }
    printf("公約數:%d\n",a);
    printf("公倍數:%d\n",num1*num2/a);
}