求最大公约数的原理是什么

希望能对你有所帮助！

辗转相除法, 又名欧几里德算法（Euclidean algorithm）乃求两个正整数之最大公因子的算法。它是已知最古老的算法, 其可追溯至前300年。它首次出现于欧几里德的《几何原本》（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的《九章算术》。它并不需要把二数作质因子分解。

证明：

设两数为a、b(b＜a)，求它们最大公约数(a、b)的步骤如下：用b除a，得a＝bq�1＋r�1（0≤r�1＜b）。若r�1=0，则(a，b)＝b；若r�1≠0，则再用r�1除b，得b＝r�1q�2＋r�2（0≤r�2＜r�1）。若r�2＝0，则(a，b)＝r�1，若r�2≠0，则继续用r�2除r�1，……如此下去，直到能整除为止。其最后一个非零余数即为(a，b)。

[编辑] 算法

辗转相除法是利用以下性质来确定两个正整数 a 和 b 的最大公因子的：

1 若 r 是 a ÷ b 的余数, 则

gcd(a,b) = gcd(b,r)

2 a 和其倍数之最大公因子为 a。

另一种写法是：

1 a ÷ b，令r为所得余数（0≤r＜b）

若 r = 0，算法结束；b 即为答案。

2 互换：置 a←b，b←r，并返回第一步。

[编辑] 虚拟码

这个算法可以用递归写成如下:

function gcd(a, b) {

if b<>0

return gcd(b, a mod b);

else

return a;

}

或纯使用循环:

function gcd(a, b) {

define r as integer;

while b ≠ 0 {

r := a mod b;

a := b;

b := r;

}

return a;

}

pascal代码（递归）

求两数的最大公约数

function gcd(a,b:integer):integer;

begin

if b=0 then gcd:=a

else gcd:=gcd (b,a mod b);

end ;

其中“a mod b”是指取 a ÷ b 的余数。

例如，123456 和 7890 的最大公因子是 6, 这可由下列步骤看出：

a b a mod b

123456 7890 5106

7890 5106 2784

5106 2784 2322

2784 2322 462

2322 462 12

462 12 6

12 6 0

只要可计算余数都可用辗转相除法来求最大公因子。这包括多项式、复整数及所有欧几里德定义域（Euclidean domain）。

辗转相除法的运算速度为 O(n2)，其中 n 为输入数值的位数。

main()

{

int i, a[3],result;

for(i=0;i<3;i++)

scanf("%d",&a[i]);

result=num(a[0],a[1]);

result=num(result,a[2]);

printf("%d\n",result);

}

int num(int p, int q)

{

int temp;

int i=p,j=q;

if(p<=0||q<=0)return (0);

do

{

if (i<j)

{

temp=i;

i=j;

j=temp;

}

for(;i>=j;i=i-j);

if (ij==0)

return (pq/(i+j));

}

while(1);

}

欧几里德如下：

欧几里德定理是指射影定律。

欧几里德算法又称辗转相除法，用于计算两个正整数a，b的最大公约数。其计算原理依赖于下面的定理： 定理：gcd(a,b) = gcd(b,a mod b) (a>b 且a mod b 不为0) 证明：a可以表示成a = kb + r，则r = a mod b 假设d是a,b的一个公约数，则有 d|a, d|b，而r = a - kb，因此d|r 因此d也是(b,a mod b)的公约数 因此(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等，得证

直角三角形射影定理，又称“欧几里德定理”，定理内容是直角三角形中，斜边上的高是两直角边在斜边上射

影的比例中项，每一条直角边是这条直角边在斜边上的射影和斜边的比例中项。

证明思路

因为射影就是将原图形的长度（三角形中称高）缩放，所以宽度是不变的，又因为平面多边形的面积比＝边长的平方比。所以就是图形的长度（三角形中称高）的比。

那么这个比值应该是平面所成角的余弦值。在两平面中作一直角三角形，并使斜边和一直角边垂直于棱（即原多边形图的平面和射影平面的交线），那么三角形的斜边和另一直角边的比值就是其多边形的长度比，即为平面多边形的面积比，而将这个比值放到该平面三角形中去运算即可。

以上就是关于求最大公约数的原理是什么全部的内容，包括:求最大公约数的原理是什么、2、 编程求三个整数的最小公倍数、欧几里德等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！