首页 > 代码库 > 欧几里得算法(辗转相除法)计算最大公约数
欧几里得算法(辗转相除法)计算最大公约数
算法定义：
两个整数x和y且x>y的最大公因子等同于y与x mod y的最大公因子。
整数t整除x和y当且仅当t整除y和x mod y，因为x等同于x mod y 加上y的一个整数倍。
另：假设最后求解到的两个数的最大公约数是1，则认为两个数互素。
1 /*递归算法*/ 2 int gcd_rec(int m, int n) 3 { 4 if (n == 0) 5 return m; 6 return gcd_rec(n, m % n); 7 } 8 9 10 /*迭代算法*/11 int gcd_iter(int m, int n)12 {13 while (m % n != 0)14 {15 int mod = m % n;16 m = n;17 n = mod;18 }19 20 return n;21 }
欧几里得算法(辗转相除法)计算最大公约数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。