辗转相除法求最大公约的方法
需积分: 1 20 浏览量
2023-11-03
21:30:25
上传
评论
收藏 14KB DOCX 举报
辗转相除法求最大公约数
辗转相除法，也称为欧几里德算法，用于求两个非负整数的最大公约数（Greatest
Common Divisor, GCD）。
算法的基本思想是：假设有两个非负整数 a 和 b，其中 a 大于等于 b。用 a 除以 b，
得到商 q 和余数 r。若 r 等于 0，则 b 即为最大公约数；若 r 不等于 0，则将 b 赋值
为 r，然后再用 b 除以新的 r，继续得到商和余数。重复这个过程，直到余数等于 0，此
时最后的除数就是最大公约数。
以下是使用辗转相除法求最大公约数的伪代码：
function gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)
例如，假设要求解最大公约数 gcd(48, 18)：
gcd(48, 18) -> gcd(18, 48 % 18) -> gcd(18, 12) -> gcd(12, 18 % 12) -> gcd(12, 6) ->
gcd(6, 12 % 6) -> gcd(6, 0) -> 6
因此，最大公约数为 6。
使用辗转相除法可以高效地求解两个整数的最大公约数，时间复杂度为 O(log(max(a,
b)))。
资源评论
