1 问题描述
Compute the Greatest Common Divisor of Two Integers using Sieve of Eratosthenes.
翻译：使用埃拉托色尼筛选法计算两个整数的最大公约数。（PS：最大公约数也称最大公因数，指两个或多个整数共有约数中最大的一个）
2 解决方案
2.1 埃拉托色尼筛选法原理简介
引用自百度百科：
埃拉托色尼筛选法(the Sieve of Eratosthenes)简称埃氏筛法，是古希腊数学家埃拉托色尼(Eratosthenes 274B.C.～194B.C.)提出的一种筛选法。 是针对自然数列中的自然数而实施的，用于求一定范围内的质数，它的容斥原理之完备性条件是p=H~。
具体求取质数的思想：
（1）先把1删除（现今数学界1既不是质数也不是合数）
（2）读取队列中当前最小的数2，然后把2的倍数删去
（3）读取队列中当前最小的数3，然后把3的倍数删去
（4）读取队列中当前最小的数5，然后把5的倍数删去
（5）如上所述直到需求的范围内所有的数均删除或读取
下面看一下执行上述步骤求不大于100的所有质数的一个示意图：
2.2 具体编码
本文求取两个数的最大公约数，采用质因数分解法：把每个数分别分解质因数，再把各数中的全部公有质因数提取出来连乘，所得的积就是这几个数的最大公约数。
例如：求24和60的最大公约数，先分解质因数，得24=2×2×2×3，60=2×2×3×5，24与60的全部公有的质因数是2、2、3，它们的积是2×2×3=12，所以，（24，60）=12。
此处，第一步，先使用埃拉托色尼筛选法求取不大于数A的所有质数，然后从这些质数中选取A的所有质因数；第二步，依照第一步思想求取数B的所有质因数；第三步，求取数A和数B公共质因数；第四步，输出数A和数B的最大公约数。
具体代码如下：
package com.liuzhen.ex1;
import java.util.Scanner;
public class SieveOfEratosthenes {
//返回一维数组，数组中的元素为不大于n的所有质数
public static int[] getPrime(int n){
int[] result1 = new int[n]; //定义一个一维数组，并从第2个元素依次初始化为相应的自然数
for(int i = 2;i < n+1;i++){
result1[i-1] = i;
}
for(int i = 2;i < n;i++){
for(int j = i+1;j < n+1;j++){
if(j % i == 0) //如果j能够整除i，使result[j-1]等于0
result1[j-1] = 0;
}
}
int[] result2 = getNoneZero(result1); //除去result数组中所有0元素
return result2; //数组中非零元素即为不大于n的所有质数
}
//返回一维数组，该数组的元素为参数数组中所有不为0的元素值
public static int[] getNoneZero(int[] A){
int len = 0;
for(int i = 0;i < A.length;i++){
if(A[i] != 0)
len = len+1;
}
int[] result = new int[len];
int k = 0;
for(int i = 0;i < A.length;i++){
if(A[i] != 0){
result[k] = A[i];
k++;
}
}
return result;
}
//求取一个数n的所有质因数(eg:24=2×2×2×3,则result[] = {2,2,2,3})
public static int[] getNprime(int n){
int[] primes = getPrime(n);
int[] result; //最终返回结果集
int len = 0; //返回结果集数组长度，初始化为0
for(int i = 0;i < primes.length;i++){
int temp = n;
while(temp % primes[i] == 0){
temp = temp/primes[i];
len++;
}
}
result = new int[len];
int k = 0;
for(int i = 0;i < primes.length;i++){
int temp = n;
while(temp % primes[i] == 0){
temp = temp/primes[i];
result[k] = primes[i];
k++;
}
}
return result;
}
//返回两个一维数组中所有共同元素
public static int[] getCommonPrime(int[] A , int[] B){
int[] result;
int lenA = A.length;
int lenB = B.length;
if(lenA < lenB){
result = new int[lenA];
for(int i = 0;i < lenA;i++){
int temp = A[i];
for(int j = 0;j < lenB;j++){
if(temp == B[j]){
result[i] = A[i];
B[j] = 0;
break;
}
}
}
}
else{
result = new int[lenB];
for(int i = 0;i < lenB;i++){
int temp = B[i];
for(int j = 0;j < lenA;j++){
if(temp == A[j]){
result[i] = B[i];
A[j] = 0;
break;
}
}
}
}
int[] result1 = getNoneZero(result);
return result1;
}
//求取数A和B的最大公约数
public static void getMaxCommonDivisor(int A,int B){
int[] primesA = getNprime(A); //数A所有质因子
int[] primesB = getNprime(B); //数B所有质因子
int[] resultPrime = getCommonPrime(primesA,primesB); //数A和数B的公共质因数
int maxCommonDivisor = 1;
System.out.println(A+"和"+B+"的公共质因数为：");
for(int i = 0;i < resultPrime.length;i++){
maxCommonDivisor *= resultPrime[i];
System.out.print(resultPrime[i]+"\t");
}
System.out.println();
System.out.print(A+"和"+B+"的最大公约数为："+maxCommonDivisor);
}
public static void main(String[] args){
System.out.println("请输入数字A和数字B的值：");
Scanner in = new Scanner(System.in);
int a = in.nextInt();
int b = in.nextInt();
getMaxCommonDivisor(a,b);
}
}
运行结果：
请输入数字A和数字B的值：
60
100和60的公共质因数为：
2 5
100和60的最大公约数为：20
请输入数字A和数字B的值：
48
60和48的公共质因数为：
2 3
60和48的最大公约数为：12
请输入数字A和数字B的值：
54
120和54的公共质因数为：
3
120和54的最大公约数为：6