January 03, 2018

欧几里得与扩展欧几里得

18冬数论作业-15121709

欧几里得算法简介与实现

欧几里得算法,又称辗转相除法,是一种古老的求最大公约数(greatest common division,GCD)的算法。辗转相除法首次出现于欧几里得的《几何原本》中,而在中国则可以追溯至东汉出现的《九章算术》。

欧几里得算法基于如下的原理:一个正整数a和b,设a<b,GCD(a, b)为a和b的最大公约数,则GCD(a, b) = GCD(a, b - a)。

由此可以写出一个基于递归的朴素欧几里得算法实现:

int __gcd(int a, int b)

{

if(a == b){

return a;

}......