在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的筛子。