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

小编典典

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

algorithm

我正在尝试找到最快的方法来检查给定数字是否为质数（在Java中）。以下是我想到的几种素数测试方法。有没有比第二个实现（isPrime2）更好的方法？

    public class Prime {

        public static boolean isPrime1(int n) {
            if (n <= 1) {
                return false;
            }
            if (n == 2) {
                return true;
            }
            for (int i = 2; i <= Math.sqrt(n) + 1; i++) {
                if (n % i == 0) {
                    return false;
                }
            }
            return true;
        }
        public static boolean isPrime2(int n) {
            if (n <= 1) {
                return false;
            }
            if (n == 2) {
                return true;
            }
            if (n % 2 == 0) {
                return false;
            }
            for (int i = 3; i <= Math.sqrt(n) + 1; i = i + 2) {
                if (n % i == 0) {
                    return false;
                }
            }
            return true;
        }
    }



public class PrimeTest {

    public PrimeTest() {
    }

    @Test
    public void testIsPrime() throws IllegalArgumentException, IllegalAccessException, InvocationTargetException {

        Prime prime = new Prime();
        TreeMap<Long, String> methodMap = new TreeMap<Long, String>();


        for (Method method : Prime.class.getDeclaredMethods()) {

            long startTime = System.currentTimeMillis();

            int primeCount = 0;
            for (int i = 0; i < 1000000; i++) {
                if ((Boolean) method.invoke(prime, i)) {
                    primeCount++;
                }
            }

            long endTime = System.currentTimeMillis();

            Assert.assertEquals(method.getName() + " failed ", 78498, primeCount);
            methodMap.put(endTime - startTime, method.getName());
        }


        for (Entry<Long, String> entry : methodMap.entrySet()) {
            System.out.println(entry.getValue() + " " + entry.getKey() + " Milli seconds ");
        }
    }
}

阅读 240

2020-07-28

共1个答案

小编典典

这是另一种方式：

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

2020-07-28