这是另一种方式：
boolean isPrime(long n) {
if(n < 2) return false;
if(n == 2 || n == 3) return true;
if(n%2 == 0 || n%3 == 0) return false;
long sqrtN = (long)Math.sqrt(n)+1;
for(long i = 6L; i <= sqrtN; i += 6) {
if(n%(i-1) == 0 || n%(i+1) == 0) return false;
}
return true;
}
并且BigInteger's isProbablePrime(...)对所有32位有效int。
编辑
请注意，isProbablePrime(certainty)这并不总是产生正确的答案。当确定性偏低时，它将产生误报，如评论中提到的@ dimo414。
不幸的是，我找不到声称isProbablePrime(certainty)对所有（32位）都有效的源int（给了足够的把握！）。
因此，我进行了一些测试。我创建了一个代表所有不均匀数字BitSet的大小，Integer.MAX_VALUE/2并使用质数筛子查找了该范围内的所有质数1..Integer.MAX_VALUE。然后，我开始i=1..Integer.MAX_VALUE进行测试new BigInteger(String.valueOf(i)).isProbablePrime(certainty) == isPrime(i)。
对于肯定性5和10，isProbablePrime(...)沿线产生假阳性。但是使用isProbablePrime(15)，没有测试失败。
这是我的测试台：
import java.math.BigInteger;
import java.util.BitSet;
public class Main {
static BitSet primes;
static boolean isPrime(int p) {
return p > 0 && (p == 2 || (p%2 != 0 && primes.get(p/2)));
}
static void generatePrimesUpTo(int n) {
primes = new BitSet(n/2);
for(int i = 0; i < primes.size(); i++) {
primes.set(i, true);
}
primes.set(0, false);
int stop = (int)Math.sqrt(n) + 1;
int percentageDone = 0, prevIoUsPercentageDone = 0;
System.out.println("generating primes...");
long start = System.currentTimeMillis();
for(int i = 0; i <= stop; i++) {
prevIoUsPercentageDone = percentageDone;
percentageDone = (int)((i + 1.0) / (stop / 100.0));
if(percentageDone <= 100 && percentageDone != prevIoUsPercentageDone) {
System.out.println(percentageDone + "%");
}
if(primes.get(i)) {
int number = (i * 2) + 1;
for(int p = number * 2; p < n; p += number) {
if(p < 0) break; // overflow
if(p%2 == 0) continue;
primes.set(p/2, false);
}
}
}
long elapsed = System.currentTimeMillis() - start;
System.out.println("finished generating primes ~" + (elapsed/1000) + " seconds");
}
private static void test(final int certainty, final int n) {
int percentageDone = 0, prevIoUsPercentageDone = 0;
long start = System.currentTimeMillis();
System.out.println("testing isProbablePrime(" + certainty + ") from 1 to " + n);
for(int i = 1; i < n; i++) {
prevIoUsPercentageDone = percentageDone;
percentageDone = (int)((i + 1.0) / (n / 100.0));
if(percentageDone <= 100 && percentageDone != prevIoUsPercentageDone) {
System.out.println(percentageDone + "%");
}
BigInteger bigInt = new BigInteger(String.valueOf(i));
boolean bigIntSays = bigInt.isProbablePrime(certainty);
if(isPrime(i) != bigIntSays) {
System.out.println("ERROR: isProbablePrime(" + certainty + ") returns "
+ bigIntSays + " for i=" + i + " while it " + (isPrime(i) ? "is" : "isn't" ) +
" a prime");
return;
}
}
long elapsed = System.currentTimeMillis() - start;
System.out.println("finished testing in ~" + ((elapsed/1000)/60) +
" minutes, no false positive or false negative found for isProbablePrime(" + certainty + ")");
}
public static void main(String[] args) {
int certainty = Integer.parseInt(args[0]);
int n = Integer.MAX_VALUE;
generatePrimesUpTo(n);
test(certainty, n);
}
}
我通过这样做来运行：
java -Xmx1024m -cp . Main 15
在我的机器上，素数的生成花费了大约30秒。而所有的实际测试i中1..Integer.MAX_VALUE花了大约2小时15分钟。
602392714
清零编程群