「java实现欧几里得」欧几里得算法过程
本篇文章给大家谈谈java实现欧几里得，以及欧几里得算法过程对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。
本文目录一览：
- 1、java代码如何实现a^-1(mod b)？
- 2、java编程：用欧几里德辗转相除法求两个正整数的最大公约数
- 3、欧几里得方法
- 4、关于欧几里得算法，主要是看不懂。请高手指点迷津。。。。
- 5、java 计算最小公倍数的问题
- 6、如何用大整数的方法编写欧几里得算法java代码实现
java代码如何实现a^-1(mod b)？
（1）用循环一个个试
（2）要快一点，试试用扩展欧几里得算法（就是利用辗转相除找最大公因数，算法过程中记录一些东西，就知道是否有逆，有逆直接可求出来），
密码学书上均有，你也可在网上找
java编程：用欧几里德辗转相除法求两个正整数的最大公约数
public class test {
public static void main(String[] args) {
// TODO Auto-generated method stub
int res = gcd(8, 6);
System.out.println(res);
}
private static int gcd(int i, int j) {
int m, n, r;
// 使mn
if (i j) {
m = i;
n = j;
} else {
m = j;
n = i;
}
// 通过辗转除来求的最大公约数
r = m % n;
while (r != 0) {
m = n;
n = r;
r = m % n;
}
// 返回最大公约数
return n;
}
}
欧几里得方法
欧几里得的方法如下：
欧几里得算法又称辗转相除法，是指用于计算两个非负整数a，b的最大公约数。应gfa用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b)。
欧几里得算法和扩展欧几里得算法可使用多种编程语言实现。
欧几里得算法是用来求两个正整数最大公约数的算法。古希腊数学家欧几里得在其著作《The Elements》中最早描述了这种算法,所以被命名为欧几里得算法。
扩展欧几里得算法可用于RSA加密等领域。
假如需要求 1997 和 615 两个正整数的最大公约数,用欧几里得算法，是这样进行的：
1997 ÷ 615 = 3 (余 152)
615 ÷ 152 = 4(余7)
152 ÷ 7 = 21(余5)
7 ÷ 5 = 1 (余2)
5 ÷ 2 = 2 (余1)
2 ÷ 1 = 2 (余0)
至此，最大公约数为1
以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数，所以就得出了 1997 和 615 的最大公约数 1。
辗转相除法是利用以下性质来确定两个正整数 a 和 b 的最大公因子的：
⒈ 若 r 是 a ÷ b 的余数，且r不为0， 则
gcd(a,b) = gcd(b,r)
⒉ a 和其倍数之最大公因子为 a。
另一种写法是：
⒈ 令r为a/b所得余数（0≤r
若 r= 0，算法结束；b 即为答案。
⒉ 互换：置 a←b，b←r，并返回第一步。
关于欧几里得算法，主要是看不懂。请高手指点迷津。。。。
1、 欧几里德算法：给定两个正整数m和n，求他们的最大公因子，即能够同时整除m和n的最大的正整数。
E1：【求余数】以n除m并令r为所得余数（我们将有0=rn）。
E2：【余数为0？】若r=0，算法结束；n即为答案。
E3：【互换】置mßn,nßr,并返回步骤E1.
证明：
我们将两个正整数m和n的最大公因子表示为：t = gcd（m，n）；
重复应用等式：gcd（m，n）= gcd（n，m mod n）直到m mod n 等于0；
m可以表示成m = kn + r；则 r = m mod n ， 假设 d是 m 和 n的一个公约数，则有：
d|m 和 d|m 而 r =m – kn ，因此 d|r ，因此 d 是 (n,m mod n) 的公约数；假设 d 是 (n,m mod n) 的公约数，
则 d|n ，d|r ，但是 m=kn+r ，因此 d 也是 (a,b) 的公约数；因此 (a,b) 和
(b,a mod b) 的公约数是一样的，其最大公约数也必然相等，得证。
具体步骤描述如下：
第一步：如果 n=0 ，返回 m 的值作为结果，同时过程结束；否则，进入第二步。
第二步：用 n 去除 m ，将余数赋给 r 。
第三步：将 n 的值赋给 m，将 r的值赋给 n，返回第一步。
伪代码描述如下：
Euclid(m,n)
// 使用欧几里得算法计算gcd(m,n)
// 输入：两个不全为0的非负整数m，n
// 输出：m，n的最大公约数
while n≠0 do
r ← m mod n
m ← n
n ← r
注：(a,b) 是 a,b的最大公因数
(a,b)|c 是指 a,b的最大公因数 可以被c整除。
java实现：
package algorithm;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class GreatestCommonDivisor {
int a,b,temp = 0;
public static void main(String args[]) throws IOException {
GreatestCommonDivisor gcd = new GreatestCommonDivisor();
gcd.readNum();
gcd.MaxNum();
System.out.print(gcd.a+"和"+gcd.b+"的最大公约数是:");
while (gcd.b != 0) {
gcd.temp = gcd.b;
gcd.b = gcd.a % gcd.b;
gcd.a = gcd.temp;
}
System.out.println(gcd.temp);
}
//输入两个正整数,中间用空格分开.
public void readNum() throws IOException{
BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
String str = buf.readLine();
for(int i = 0;istr.length();i++){
if(str.charAt(i)==' ' temp == 0){
a = Integer.parseInt(str.substring(temp,i));
temp = i;
b = Integer.parseInt(str.substring(temp+1,str.length()));
break;
}
}
}
public void MaxNum(){
if (a b) {
temp = b;
b = a;
a = temp;
}
}
}
java 计算最小公倍数的问题
汗,这是欧几里得算法求最大公约数..
int r=m%n;
while(r!=0)
{ m=n;
n=r;
r=m%n;
}
这是欧几里得算法的实现...
欧几里德算法又称辗转相除法，用于计算两个整数a，b的最大公约数。其计算原理依赖于下面的定理：
定理：gcd(a,b) = gcd(b,a mod b)
证明：a可以表示成a = kb + r，则r = a mod b
假设d是a,b的一个公约数，则有
d|a, d|b，而r = a - kb，因此d|r
因此d是(b,a mod b)的公约数
假设d 是(b,a mod b)的公约数，则
d | b ， d |r ，但是a = kb +r
因此d也是(a,b)的公约数
因此(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等，得证
如何用大整数的方法编写欧几里得算法java代码实现
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int a, b;
a = scanner.nextInt();
b = scanner.nextInt();
System.out.printf("%d和%d的最大公约数为：%d", a, b, Gcd(a, b));
}
private static int Gcd(int M, int N) {
int Rem;
while (N 0) {
Rem = M % N;
M = N;
N = Rem;
}
return M;
java实现欧几里得的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于欧几里得算法过程、java实现欧几里得的信息别忘了在本站进行查找喔。