求兩個正整數最大公約數用到輾轉相除法。
方法：一、a/b，令r為所得餘數(0≤r<b)
若r=0，結束，b為答案；
二、否則，令a=b, b=r并返回第一步。
實現的代碼：
1 #include<stdio.h> 2 int main() 3 { 4 int a,b,r; 5 scanf("%d%d",&a,&b); 6 r=a%b; //第一次求餘數 7 while(r!=0) 8 { 9 a=b; //輾轉相除法 10 b=r; 11 r=a%b; 12 } 13 printf("%d\n",b); 14 return 0; 15 }
利用一個公式同時可以求兩個數的最小公倍數lcm：
lcm=a*b/gcd(a,b)
原文：http://www.cnblogs.com/houraisan-kaguya/p/4119148.html