辗转相除

辗转相除，又名欧几里德算法(Euclidean algorithm)，乃求两个正整数之最大公约数的算法。它是已知最古老的算法, 其可追溯至公元前300年。它是已知最古老的算法, 其可追溯至公元前300年。它首次出现于欧几里德的《几何原本》(第VII卷，命题i和ii)中，而在中国则可以追溯至东汉出现的《九章算术》。它并不需要把二数作质因子分解。