正文
欧几里得的JAVA代码 欧几里得算法mod
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
欧几里得算法减法伪代码
欧几里得算法减法伪代码如下：
1.将被减数赋给大整数A， 减数赋给B
2.判断A和B大小：如果A B，跳到第3步，A B，交换A和B的值，并跳到第3步
3.循环执行以下步骤，直到B=0：
a. 将A的最高位与B的最高位比较，如果A的最高位大于B的最高位，则A = A - B，否则A = A + B
b. 把A的最高位移除并把A的位数减1
c. 把B的最高位移除并把B的位数减1
4. 返回A的值
相关问答
Q1: 求一个用java编写的1到100内的素数，并且每行输出5个素数
public class Test {
public static void main(String[] args) {
int i, count = 0;
for(i=2; i=100; i++){
if(isPrimeNumber(i) == true){
count++;
System.out.printf("%6d", i);
if(count%5 == 0){
System.out.println();
}
}
}
//判断一个数是否是素数，若是，返回true，否则返回false
public static boolean isPrimeNumber(int num){
int k = (int) Math.sqrt(num);
if(num == 2){
return true;
for(int i=2; i=k; i++)
if(num%i == 0)
return false;
return true;
}
}
扩展：
质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数；否则称为合数。
质数的个数是无穷的。欧几里得的《几何原本》中有一个经典的证明。它使用了证明常用的方法：反证法。具体证明如下：假设质数只有有限的n个，从小到大依次排列为p1，p2，……，pn，设N=p1×p2×……×pn，那么，
是素数或者不是素数。
如果
为素数，则
要大于p1，p2，……，pn，所以它不在那些假设的素数集合中。
如果 为合数，因为任何一个合数都可以分解为几个素数的积；而N和N+1的最大公约数是1，所以不可能被p1，p2，……，pn整除，所以该合数分解得到的素因数肯定不在假设的素数集合中。因此无论该数是素数还是合数，都意味着在假设的有限个素数之外还存在着其他素数。所以原先的假设不成立。也就是说，素数有无穷多个。
其他数学家给出了一些不同的证明。欧拉利用黎曼函数证明了全部素数的倒数之和是发散的，恩斯特·库默的证明更为简洁，哈里·弗斯滕伯格则用拓扑学加以证明。
Q2: 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;
}
}
Q3: java算法题。小菜鸟的大问题。面试题。
帮你写出来了：用 欧几里得最大公约数 算法，然后判断：
如果分子 = 分母或者 gcd 结果 b 值不是 1 就不是最简真分数，否则就是。
我这个用正则表达式先判断输入格式了。
---------------------------------------------------------------
import java.util.regex.Pattern;
import java.io.*;
public class Demo {
public static void main (String args[]) throws IOException {
Pattern regex = Pattern.compile("[0-9]*/[0-9]*");
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String num = "";
while (!(num = br.readLine()).equals("-1")) {
if (!regex.matcher(num).matches()) {
System.out.println("格式不正确，请重新输入！");
continue;
}
int a = Integer.parseInt(num.substring(0, num.indexOf('/')));
int b = Integer.parseInt(num.substring(num.indexOf('/')+1));
if (a = b || !isRelativelyPrime(a, b))
System.out.println(num + "不是最简真分数");
else
System.out.println(num + "是最简真分数");
}
}
private static boolean isRelativelyPrime (int a, int b) {
int tmp = 0;
while (a 0) {
tmp = b % a;
b = a;
a = tmp;
}
if (b == 1)
return true;
else
return false;
}
}
----------------------------- 运行结果 -------------------------------
Q4: 关于欧几里得算法，主要是看不懂。请高手指点迷津。。。。
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代码和欧几里得算法mod的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。
