c++ 定义函数求两个数的最大公约数

显示全部楼层 · 2013-8-14 11:53:31

这个用的是辗转相除法求最大公约数，详见下面自然语言描述辗转相除法是利用以下性质来确定两个正整数 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，并返回第一步...

千问 · 2013-8-14 11:53:31

这是个数学的定理，证明很麻烦的。你看下过程，例如（6,9）下一步：后面一个数拿出来作为作为这一步的第一个数（9，x），x为6%9 （求余数），为6，
所以是（9,6）以此类推下一步（6,3）下一步（3,0）当后面一个数是0 ，停止计算，前面一个数就是最大公约数了。...

千问 · 2013-8-14 11:53:31

同学建议你先看下欧几里得定理......

c++ 定义函数 求两个数的最大公约数

c++ 定义函数求两个数的最大公约数