在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

这是另一种方式:

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

Answer 2

这是最优雅的方式:

public static boolean isPrime(int n) {
    return !new String(new char[n]).matches(".?|(..+?)\\1+");
}

Java 1.4+.不需要进口.

这么短.如此美丽.

Answer 3

看看AKS素性测试(及其各种优化).它是在多项式时间内运行的确定性素性测试.

这里有来自Tuebingen大学(德国)的 Java算法的实现

Answer 4

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

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

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

Answer 5

我认为这个方法是最好的。至少对于我来说-

    public static boolean isPrime(int num)
    {
        for (int i = 2; i<= num/i; i++)
        {
            if (num % i == 0)
            {
                return false;
            }
        }
        return num > 1;
    }

Answer 6

对于相当小的数字，您的算法将很好地工作。对于大数字，应使用高级算法（例如基于椭圆曲线）。另一个想法是使用一些“伪素数”测试。这些将快速测试一个数字是否是素数，但它们并不是 100% 准确。但是，它们可以帮助您比使用算法更快地排除某些数字。

最后，尽管编译器可能会为您优化这一点，但您应该编写：

int max =  (int) (Math.sqrt(n) + 1);
for (int i = 3; i <= max; i = i + 2) {
}

Answer 7

Jaeschke (1993) 提出的快速测试是 Miller-Rabin 测试的确定性版本，它没有低于 4,759,123,141 的误报，因此可以应用于 Java int。

// Given a positive number n, find the largest number m such
// that 2^m divides n.
private static int val2(int n) {
  int m = 0;
  if ((n&0xffff) == 0) {
    n >>= 16;
    m += 16;
  }
  if ((n&0xff) == 0) {
    n >>= 8;
    m += 8;
  }
  if ((n&0xf) == 0) {
    n >>= 4;
    m += 4;
  }
  if ((n&0x3) == 0) {
    n >>= 2;
    m += 2;
  }
  if (n > 1) {
    m++;
  }
  return m;
}

// For convenience, handle modular exponentiation via BigInteger.
private static int modPow(int base, int exponent, int m) {
  BigInteger bigB = BigInteger.valueOf(base);
  BigInteger bigE = BigInteger.valueOf(exponent);
  BigInteger bigM = BigInteger.valueOf(m);
  BigInteger bigR = bigB.modPow(bigE, bigM);
  return bigR.intValue();
}

// Basic implementation.
private static boolean isStrongProbablePrime(int n, int base) {
  int s = val2(n-1);
  int d = modPow(base, n>>s, n);
  if (d == 1) {
    return true;
  }
  for (int i = 1; i < s; i++) {
    if (d+1 == n) {
      return true;
    }
    d = d*d % n;
  }
  return d+1 == n;
}

public static boolean isPrime(int n) {
  if ((n&1) == 0) {
    return n == 2;
  }
  if (n < 9) {
    return n > 1;
  }

  return isStrongProbablePrime(n, 2) && isStrongProbablePrime(n, 7) && isStrongProbablePrime(n, 61);
}

这不适用于long变量，但有一个不同的测试：BPSW 测试没有高达 2^64 的反例。这基本上包括一个像上面这样的 2-strong probable prime test，然后是一个更复杂但没有根本区别的强 Lucas 测试。

这两项测试都比任何类型的试验部门都要快得多。