用Java测试原始性最快的方法是什么？

用Java测试原始性最快的方法是什么？

这是另一种方式：

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'sisProbablePrime(...)

对所有32位有效

int

。

编辑

请注意，

isProbablePrime(certainty)

这并不总是产生正确的答案。当确定性偏低时，它将产生误报，如评论中提到的@ dimo414。

不幸的是，我找不到声称

isProbablePrime(certainty)

对所有（32位）都有效的源

int

（给了足够的把握！）。

因此，我进行了一些测试。我创建了一个代表所有不均匀数字

BitSet

的大小，

Integer.MAX_VALUE/2

并使用质数筛子查找了该范围内的所有质数

1..Integer.MAX_VALUE

。然后，我开始

i=1..Integer.MAX_VALUE

进行测试

newBigInteger(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分钟。