在Java中测试primality的最快方法是什么？

Question

我试图找到检查给定数字是否为素数的最快方法（在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 ");        }    }}

Answer 1

你迈出了消除2的所有倍数的第一步。

但是，你为什么要止步呢？你可以消除所有3的倍数，除了3，所有5的倍数除了5，等等。

当你按照这个推理得出结论时，你会得到Eratosthenes的筛子。