今天來研究下通過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毫秒
以上是關于最大索數計算的小探索，希望有興趣的朋友可以幫看下上面的算法能否進一步優化，算出更大的結果。
