辗转相除法 求两个正整数的最大公约数 gcd(a,b) 算法思路 s1: 将两整数求余 a%b = x s2: 如果x = 0;则b为最大公约数 s3: 如果x != 0,则 a = b;b = x;继续从s1开始执行 流程图 例析 例如,求gcd(319,377) 首先(319,377)与(377,319)的最大公约数相同;即:gcd(319,377) == gcd(377,319) s1: 因为377÷319 商1(余58) 所以(377,319)==(319,58) 即:a←b, b←a%b; s2: 因为319÷58商5(余29) 所以(319,58)==(58,29) 即:a←b, b←a%b; S3: 因为58÷29商2(余0) 所以(58,29)==29 即: a%b==0;b为最大公约数 也就是说,求两个数的最大公约数时,先用较大数除以较小数得到余数,如果余数为零,则最大公约数就等于较小数;否则用较小数代替较大的数,再用刚求得的余数代替较小的数,继续求余操作,直到余数为零。 PY代码实现 #辗转相除法 def myGcd(a,b): x = a % b while (x != 0): a = b b = x x = a % b return b