欧几里得算法

简介: // ,暂时还没有想通原理 // 返回最大公因子,要求 m,n 为正整数pubic static int maxSub(int m, int n){ // 保证 m >= n if(m < n){ int temp = n; m = n; n = temp; } // 取模 int r = m % n; // 可以整除,那么小的数字就是最大公因子 if(0 == r){ return n; } // 否则。

// ,暂时还没有想通原理

// 返回最大公因子,要求 m,n 为正整数
pubic static int maxSub(int m, int n){
	// 保证 m >= n
	if(m < n){
		int temp = n;
		m = n;
		n = temp;
	}
	// 取模
	int r = m % n;
	// 可以整除,那么小的数字就是最大公因子
	if(0 == r){
		return n;
	}
	// 否则。递归调用, 算出小值与差值的最大公因子
	return maxSub(n, r);
}

// 大致的思路是,既然m 和 n 之间取模相差了 r, 那么,这个最大公因子自然是比r要小了,并且是 r 和n的最大公约数。

// 目前还没有想通数学原理, 欢迎讨论。

目录
相关文章
|
3月前
【刷题记录】最大公因数,最小公倍数(辗转相除法、欧几里得算法)
【刷题记录】最大公因数,最小公倍数(辗转相除法、欧几里得算法)
|
6月前
|
算法 数据安全/隐私保护
什么是扩展欧几里得算法?
【5月更文挑战第13天】什么是扩展欧几里得算法?
104 3
宝藏例题(欧几里得算法+素数的三种境界………)
宝藏例题(欧几里得算法+素数的三种境界………)
宝藏例题(欧几里得算法+素数的三种境界………)
|
6月前
|
算法 Python
Python欧几里得算法找最大公约数
Python欧几里得算法找最大公约数
55 0
|
6月前
|
算法 搜索推荐 程序员
C语言第二十二练——扩展欧几里得算法
C语言第二十二练——扩展欧几里得算法
60 0
P4057 [Code+#1]晨跑(数学分析,辗转相除法模板(欧几里得算法))
P4057 [Code+#1]晨跑(数学分析,辗转相除法模板(欧几里得算法))
54 0
|
算法 搜索推荐 程序员
欧几里得算法
欧几里得算法(Euclidean algorithm)是一种计算两个数的最大公约数(Greatest Common Divisor,简称 GCD)的算法。欧几里得算法的基本思想是通过辗转相除的方式,将两个数逐步缩小,直到它们的公约数为止。欧几里得算法的时间复杂度为 O(log n)。
212 1
|
算法 Java
欧几里得算法(GCD, 辗转相除法)
欧几里得算法(GCD, 辗转相除法)
数论整理之欧几里得算法gcd
数论整理之欧几里得算法gcd
|
存储 算法 搜索推荐
Jave 关于部分Math类和欧几里得算法
Jave 关于部分Math类和欧几里得算法