java求最大公约数（分解质因数）

下面是四种用java语言编程实现的求最大公约数的方法：

package gcd;import java.util.ArrayList;
import java.util.List;public class gcd {
public static void main(String[] args) {
long startTime;
long endTime;
long durationTime;int[] testArray1 = new int[]{784, 988, 460, 732, 548, 998, 672, 1024, 888, 512};
int[] testArray2 = new int[]{1024, 82, 92, 128, 58, 2014, 512, 88, 582, 788};for (int i = 0; i < 10; i++) {
startTime = System.nanoTime();
System.out.println("欧几里得方法：" + Euclid(testArray1[i],testArray2[i]));
endTime = System.nanoTime();
durationTime = endTime - startTime;
System.out.println("欧几里得算法耗时：" + durationTime + "\n");startTime = System.nanoTime();
System.out.println("连续整数检測法：" + consecutiveIntegersTest(testArray1[i], testArray2[i]));
endTime = System.nanoTime();
durationTime = endTime - startTime;
System.out.println("连续整数检測算法耗时：" + durationTime + "\n");startTime = System.nanoTime();
System.out.println("辗转相减法：" + consecutiveSubstract(testArray1[i], testArray2[i]));
endTime = System.nanoTime();
durationTime = endTime - startTime;
System.out.println("辗转相减算法耗时：" + durationTime + "\n");startTime = System.nanoTime();
System.out.println("分解质因数法：" + primeFactors(testArray1[i], testArray2[i]));
endTime = System.nanoTime();
durationTime = endTime - startTime;
System.out.println("分解质因数算法耗时：" + durationTime);
}}/**
* 欧几里得算法求最大公约数
* @param no1
* @param no2
* @return
*/
public static int Euclid(int no1, int no2) {
int remainder;
remainder = no1%no2;
while(remainder != 0) {
no1 = no2;
no2 = remainder;
remainder = no1%no2;
}
return no2;
}/**
* 连续整数检測法
* @param m
* @param n
* @return
*/
public static int consecutiveIntegersTest(int m, int n) {
int t;
if (m > n)
t = n;
else
t = m;
while(true) {
if (m%t == 0 && n%t == 0)
break;
else
t = t - 1;
}
return t;
}/**
* 辗转相减法
* @param num1
* @param num2
* @return
*/
public static int consecutiveSubstract(int num1, int num2) {
while(true) {
if (num1 > num2)
num1 -= num2;
else if (num1 < num2)
num2 -= num1;
else
return num1;
}
}/**
* 分解质因数法
* @param primeNum1
* @param primeNum2
* @return
*/
public static int primeFactors(int primeNum1, int primeNum2) {
int prime_gcd = 1;
int compareListSize;
int temp1, temp2;
int pn1 = primeNum1, pn2 = primeNum2;
List<Integer> num1List = new ArrayList<Integer>();
List<Integer> num2List = new ArrayList<Integer>();
List<Integer> sameNumList = new ArrayList<Integer>();
//求出质因数
for (int i = 2; i < pn1/2;) {//注意此处用的是pn1，而不是primeNum1，primeNum1的值在以下的运行过程会不断减小
if (primeNum1%i == 0) {//求余数，假设能被整除，返回true
temp1 = primeNum1 / i;//求商
primeNum1 = temp1;//将商赋值给primeNum1。又一次推断余数是否为0
num1List.add(i);//将质因数放入num1List
} else if (primeNum1%i != 0) {
i = i + 1;//假设余数不等于0。除数i加1，继续求余数
}
}for (int i = 2; i < pn2/2;) {
if (primeNum2%i == 0) {
temp2 = primeNum2 / i;
primeNum2 = temp2;
num2List.add(i);
} else if (primeNum2%i != 0) {
i = i + 1;
}
}
int num1ListSize = num1List.size();
int num2ListSize = num2List.size();
if (num1ListSize < num2ListSize) {
for (int i = 0; i < num1List.size();) {
if (num2List.contains(num1List.get(i))) {
prime_gcd *= num1List.get(i);
num2List.remove(num2List.indexOf(num1List.get(i)));
num1List.remove(i);
if (num1List.size() == 0 || num2List.size() == 0)
break;
} else {
i = i + 1;
}
}
} else {
for (int i = 0; i < num2List.size(); ) {
if (num1List.contains(num2List.get(i))) {
prime_gcd *= num2List.get(i);
num1List.remove(num1List.indexOf(num2List.get(i)));
num2List.remove(i);
if (num1List.size() == 0 || num2List.size() == 0)
break;
} else {
i = i + 1;
}
}
}
return prime_gcd;
}
}