利用輾轉相除法求兩個自然數的最大公因數 程序如下：
//利用輾轉相除法求兩個自然數的最大公因數
int gcd(int a, int b)
{
int r;
while(b)
{
r = a%b;
a = b;
b = r;
}
return a;
}
相關理論如下：
「輾轉相除法」又叫做「歐幾里得算法」，是公元前 300 年左右的希臘數學家歐幾里得在他的著作《幾何原本》提出的。利用這個方法,可以較快地求出兩個自然數的最大公因數，即 HCF 或叫做 gcd。所謂最大公因數，是指幾個數的共有的因數之中最大的一個，例如 8 和 12 的最大公因數是 4，記作 gcd(8,12)=4。
在介紹這個方法之前,先說明整除性的一些特點,注以下文的所有數都是正整數,以后不再重覆.
我們可以這樣給出整除以的定義:
對於兩個自然數 a 和 b，若存在正整數 q，使得 a=bq，則 b 能整除 a，記作 b | a，我們叫 b 是 a 的因數，而 a 是 b 的倍數。那麼如果 c | a，而且 c | b，則 c 是 a 和 b 的公因數。
由此,我們可以得出以下一些推論：
推論一：如果 a | b，若 k 是整數，則 a | kb。因為由 a | b 可知 ha=b，所以 (hk)a=kb，即 a | kb.
推論二：如果 a | b 以及 a | c，則 a | (b±c)。因為由 a | b 以及 a | c，可知 ha=b，ka=c，二式相加,得 (h+k)a=b+c,即 a | (b+c).同樣把二式相減可得 a | (b-c)。
推論三：如果 a | b 以及 b | a，則 a=b。因為由 a | b 以及 b | a，可知 ha=b，a=kb，因此 a=k(ha)，hk=1，由於 h 和 k 都是正整數，故 h=k=1，因此 a=b。
輾轉相除法是用來計算兩個數的最大公因數，在數值很大時尤其有用而且應用在電腦程式上也十分簡單。其理論如下：
如果 q 和 r 是 m 除以 n 的商及余數，即 m=nq+r，則 gcd(m,n)=gcd(n,r)。 證明是這樣的:
設 a=gcd(m,n)，b=gcd(n,r)
則由 a | m 及 a | n，可得 a | (m-nq)(由推論一及推論二得出的)，即 a | r ，又 a | n，所以 a | b。
由 b | r 及 b | n，可得 b | (nq+r)，即 b | m，又 b | n，所以b | a。
因為 a | b 并且 b | a，所以 a=b，即 gcd(m,n)=gcd(n,r)。
舉例計算 gcd(546, 429),由於 546=1(429)+117,429=3(117)+78,117=1(78)+39,78=2(39),因此
gcd(546, 429)
=gcd(429, 117)
=gcd(117, 78)
=gcd(78, 39)
=39
此處再添加一個程序例子，不過不是利用輾轉相除法
求最大公約數和最小公倍數:
#include <iostream>
using namespace std;
int gec,lcm;
void process(int x,int y)
{
gcd=x<y?x:y;
lcm=x<y?y:x;
for(gcd=x<y?x:y;gcd>1;gcd--)if(x%gcd==0&&y%gcd==0)break;
for(lcm=x<y?x:y;lcm>1;lcm++)if(lcm%x==0&&lcm%y==0)break;
return;
}