JAVA计算指定上限的最大素数
今天来研究下通过JAVA进行指定上限的最大素数的计算。比如指定上限为1亿，通过程序算出结果为99999989，即不超过1亿的最大素数为99999989。
网上搜索到了这个问题的一种解法如下，我们命名为算法1：
/*
* 使用对撞指针,步长为1
*/
public static int maxPrime1(int num) {
int i = num;
while (i > 1) {
int m = 2, n = i - 1;
while (m <= n) {
if (m * n == i) {
break;
} else if (m * n > i) {
n--;
} else {
m++;
}
}
if (m > n) {
return i;
}
i--;
}
return 1;
}
为了调用上面的代码，主函数如下：
public static void main(String[] args) {
long beginTime = System.currentTimeMillis();
BigInteger num=new BigInteger(getNum(8));
System.out.println("最大素数: " + maxPrime1(num.intValue()));
// System.out.println("最大素数: " + maxPrime2(num.intValue()));
// System.out.println("最大素数: " + maxPrime3(num.longValue()));
// System.out.println("最大素数: " + maxPrime4(num));
// System.out.println("最大素数: " + maxPrimeSet(num.longValue()));
long endTime=System.currentTimeMillis();
System.out.println("用时："+(endTime- beginTime)+"毫秒");
}
其中getNum是为了返回10的n次方的数，定义如下：
public static String getNum(int n){
String num="1";
for(int i=0;i<n;i++){
num=num+"0";
}
return num;
}
算法1在输入为10的8次方(即1亿)时，用时1102毫秒。输入为10的9次方时，算法1就力不从心了，算了超过10秒还没有出来结果。
从算法上来看，主要的问题在于n往下减的速度太慢，每次都减1，其实n可以一步到位算出，优化后得到算法2：
/*
* 使用对撞指针,下限步长为1，上限一步到位
*/
public static int maxPrime2(int num) {
int i = num;
while (i > 1) {
int m = 2, n = i/m;
while (m <= n) {
if (m * n == i) {
break;
} else if (m * n > i) {
n=i/m;
} else {
m++;
}
}
if (m > n) {
return i;
}
i--;
}
return 1;
}
算法2在输入为10的8次方时，用时1毫秒。输入为10的9次方时，用时也是1毫秒。输入为10的10次方时，超过了JAVA中int类型的上限，不能计算了。
于是修改算法2的输入类型，由int换成long，修改后得到算法3：
/*
* 使用对撞指针,下限步长为1，上限一步到位
*/
public static long maxPrime3(long num) {
long i = num;
while (i > 1) {
long m = 2, n = i/m;
while (m <= n) {
if (m * n == i) {
break;
} else if (m * n > i) {
n=i/m;
} else {
m++;
}
}
if (m > n) {
return i;
}
i--;
}
return 1;
}
算法3在输入为10的10次方时，用时7毫秒。输入为10的15次方时，用时也是893毫秒。输入为10的16次方时，用时是5299毫秒，得到最大素数为9999999999999937。输入为10的17次方时，算了超过10秒还没有出来结果。
因为long还是有数值的限制，于是考虑换成没有限制的BigInteger，得到算法4：
/*
* 使用对撞指针,下限步长为1，上限一步到位
*/
public static BigInteger maxPrime4(BigInteger num) {
BigInteger i = num;
BigInteger num1 = new BigInteger("1");
while (i.compareTo( num1) > 0) {
BigInteger m = new BigInteger("2"), n = i.divide(m);
while (m.compareTo(n) <= 0) {
BigInteger i2=m.multiply( n);
if (i2.compareTo(i) == 0) {
break;
} else if (i2.compareTo(i)> 0) {
n=i.divide(m);
} else {
m=m.add(num1);
}
}
if (m.compareTo(n) > 0) {
return i;
}
i=i.subtract(num1);
}
return num1;
}算法4在输入为10的15次方时，用时8974毫秒。输入为10的16次方时，算了超过10秒还没有出来结果。由此可见BigInteger的计算消耗比long要大，优点是没有数据的上限的限制。
以上4种算法的效率对比如下：
另外也测了下指定上限算出全部素数的算法，代码如下：
/*
* 使用对撞指针,下限步长为1，上限一步到位
*/
public static long maxPrimeSet(long num) {
Set<Long> primes=new HashSet<Long>();
Long maxPrime=2L;
primes.add(maxPrime);
for(long i=3;i<=num;i++){
boolean isPrime=true;
for (long prime : primes) {
if(i/prime*prime==i) {
isPrime=false;
break;
}
}
if(isPrime) {
maxPrime=i;
primes.add(maxPrime);
}
}
System.out.println("素数个数："+primes.size());
return maxPrime;
}
结果最大输入为10的5次方(再增加超过10秒还没有结果)，输出如下：
素数个数：9592
最大素数: 99991
用时：2747毫秒
以上是关于最大索数计算的小探索，希望有兴趣的朋友可以帮看下上面的算法能否进一步优化，算出更大的结果。