用輾轉相除法來求。

<1> 用輾轉相除法求最大公約數

演算法描述:

m對n（在這裡，m>n）求餘為r, 若r不等於0

則 m <- n, n <- r, 繼續求餘

否則 n 為最大公約數

<2> 最小公倍數 = 兩個數的積 / 最大公約數

程式：

#include "stdio.h"

main()

{

int m,n,num1,num2,r,cup;

scanf("%d,%d",&num1,&num2);

if(num1<num2)

{

cup=num1;

num1=num2;

num2=cup;

}

m=num1;

n=num2;

r=m%n;

while(r)

{

m=n;

n=r;

r=m%n;

}

printf("zui da gong yue shu shi:%d\n",n);

printf("zui xiao gong bei shu shi:%d\n",num1*num2/n);

}

**********************************************

用輾轉相除法求兩個數的最大公約數的步驟如下：

先用小的一個數除大的一個數，得第一個餘數；

再用第一個餘數除小的一個數，得第二個餘數；

又用第二個餘數除第一個餘數，得第三個餘數；

這樣逐次用後一個數去除前一個餘數，直到餘數是0為止。那麼，最後一個除數就是所求的最大公約數（如果最後的除數是1，那麼原來的兩個數是互質數）。

例如求1515和600的最大公約數，

第一次：用600除1515，商2餘315；

第二次：用315除600，商1餘285；

第三次：用285除315，商1餘30；

第四次：用30除285，商9餘15；

第五次：用15除30，商2餘0。

1515和600的最大公約數是15。

輾轉相除法是求兩個數的最大公約數的方法。如果求幾個數的最大公約數，可以先求兩個數的最大公約數，再求這個最大公約數與第三個數的最大公約數。這樣依次下去，直到最後一個數為止。最後所得的一個最大公約數，就是所求的幾個數的最大公約數。