辗转相除法例题（辗转相除法）

大家好,乐乐来为大家解答以下的问题，关于辗转相除法例题，辗转相除法这个很多人还不知道,那么今天让乐乐带着大家一起来看看吧！

辗转相除法 辗转相除法, 又名欧几里德算法（Euclidean algorithm）乃求两个正整数之最大公因子的算法。

它是已知最古老的算法, 其可追溯至前300年。

它首次出现于欧几里德的《几何原本》（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的《九章算术》。

它并不需要把二数作质因子分解。

[编辑] 算法 辗转相除法是利用以下性质来确定两个正整数 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 (a 不整除 b) 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; } 其中“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 为输入数值的位数。

本文分享到此完毕，希望对您有所帮助。

　　免责声明：本文由用户上传，与本网站立场无关。财经信息仅供读者参考，并不构成投资建议。投资者据此操作，风险自担。 如有侵权请联系删除！