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

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 ");
        }
    }
}

- Anantha Kumaran

---

如果您需要确定该数字是100%的质数，那么您的解决方案是最佳的。 - Aurril

JUnit @Test 注解赢了 ;) - basszero

@maaartinus，我在USACO培训计划的教程中读到过这样一句话：“一些热衷于优化的程序员喜欢将a/4改为(a>>2)以节省时间...现代编译器已经了解这一点，并自动执行这样的替换，因此更好的程序员可以写出他们想要的a/4。”这只是一个思考的问题。 - SimonT

@SimonT：问题在于a/4与a>>2不同，因为负数会向上舍入而不是向下。除非编译器能够证明a>=0，否则它必须生成一个相当复杂的表达式来避免除法（仍然是一种改进，但大约需要3个周期而不是单个指令）。 - maaartinus

你需要这个是做什么的？你的数字有多大（几位数）？你需要测试多大范围内的多少个数字？ - starblue

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的isProbablePrime(...)对于所有32位int都有效。

编辑

请注意，isProbablePrime(certainty)并不总是产生正确的答案。当确定性较低时，它会产生误报，正如@dimo414在评论中提到的那样。

不幸的是，我找不到声称isProbablePrime(certainty)对于所有（32位）int都有效（给定足够的确定性！）的来源。

因此，我进行了一些测试。我创建了一个大小为Integer.MAX_VALUE/2的BitSet，表示所有奇数，并使用素数筛选器在范围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秒。而对于1..Integer.MAX_VALUE中的所有i进行实际测试则需要约2小时15分钟。

- Bart Kiers

---

(long)Math.sqrt(n) 应该改为 (long)Math.sqrt(n)+1。 - Bart Kiers

isPrime3 2213毫秒 isPrime2 3039毫秒 isPrime1 6030毫秒你打败了我 - Anantha Kumaran

你说的BigInteger有源头或证据吗？你使用了哪种确定性？我曾看到isProbablePrime（1）在数字9上失败，因此你回答中的暗示它总是有效显然是错误的。但是你可以信任int /是质数/的确定性有多少？long呢？ - dimo414

由于这是Java isprime搜索的第一个结果，我认为强调此答案中的缺陷很重要。对于每个确定性，都有可能得到错误的答案。这是因为isProbablePrime使用随机实例选择证人（并且根据数字的长度，甚至覆盖了确定性）。例如：http://ideone.com/t3lo9G - tb-

你只需要一个16位质数列表，就可以100%确定地将任何32位整数除以它们。 - juanmf

Answer 2

这是最优雅的方式：

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

Java 1.4+。无需导入。

如此简短。如此美丽。

- user102008

---

这个正则表达式基本上是对一个一元数进行试除法。它在Perl中被提到了很多次；你可以在许多网站上看到它的解释，例如https://dev59.com/8nA75IYBdhLWcg3wYH3I http://www.noulakaz.net/weblog/2007/03/18/a-regular-expression-to-check-for-prime-numbers/。在Java中唯一的区别是：1)`.matches()`匹配整个字符串，所以不需要使用`^`和`$`；2)我没有像在Java中那样重复使用`1`（这很难实现），而是创建了一个全空字符的字符串（通过创建一个新的`char`数组），然后用`.`匹配它们。 - user102008

如果“优雅”意味着“聪明而简洁”，那当然可以。如果“优雅”意味着“可读性强”，我会说不行。我肯定不希望在代码中遇到这种情况。 - Paul Cantrell

比起最简单的算法，它要慢数万倍。 - Esailija

这件事情并不优雅。 - wvdz

正则表达式本质上等同于用正整数序列除以待判断的数，这是一种“最坏情况”下的“朴素”解法，用于判断一个数是否为质数。 - Samveen

Answer 3

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

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

当你将这种推理推导到最后，你就会得到埃拉托斯特尼筛法。

- Jimmy

---

在for循环的前两次迭代中，3和5的倍数将被消除。埃拉托斯特尼筛法对于生成一系列素数特别有效（依我之见）。 - Anantha Kumaran

你的意思不是指幂，而是倍数。 - principal-ideal-domain

Answer 4

请看一下AKS素数测试（以及其各种优化）。它是一个确定性素性测试，运行时间为多项式时间。

这里有一份Java实现算法的代码来自德国图宾根大学的网站

- Brandon E Taylor

---

维基百科：「虽然 AKS 算法在理论上非常重要，但在实践中并不使用。对于 64 位输入，Baillie-PSW 算法是确定性的，并且运行速度比 AKS 快多个数量级。对于更大的输入，ECPP 和 APR 测试的表现远优于 AKS（也是无条件正确的）。」这就是在定义 O(n) 时省略乘法常数的实际后果。 - Honza Zidek

即使链接的实现说“因此，AkS测试只与计算复杂性理论有关。使用高效的实现测试2^13-1大约需要30分钟。”测试8191这个数字需要30分钟。这是一种非常缓慢的测试方式。虽然有更快的AKS版本，但它仍然不是这个问题的好答案。 - DanaJ

实现链接似乎又失效了，但仍然可以在archive.org中找到：https://web.archive.org/web/20150717104434/http://www-ti.informatik.uni-tuebingen.de:80/~reinhard/krypto/AKSTest/AKSeng.html - l'L'l

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;
    }

- Ariful Islam

Answer 6

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-强概率素数测试，后面再跟一个强Lucas测试，稍微有些复杂但并不根本不同。

这两个测试都比任何试除法都要快得多。

- Charles

Answer 7

对于较小的数字，您的算法将运行良好。对于大数字，应使用高级算法（例如基于椭圆曲线）。另一个建议是使用一些“伪质数”测试。它们可以快速测试数字是否为质数，但不是100％准确的。然而，它们可以帮助您比使用您的算法更快地排除某些数字。

最后，虽然编译器可能会为您进行优化，但您应该编写：

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

- kgiannakakis

Answer 8

如果你只是想确定一个数字是否为质数，那就已经足够了。但是，如果你想从0到n找到所有的质数，更好的选择将是埃拉托色尼筛法。但这将取决于Java对数组大小等方面的限制。

- saugata

Answer 9

当然有数百种素性测试，都基于数字大小、特殊形式、因子大小等各种优缺点。

然而，在Java中我发现最有用的是这个：

BigInteger.valueOf(long/int num).isProbablePrime(int certainty);

这个已经实现了，速度相当快（我发现用填充有长整数0-2 ^ 64和确定性为15的1000x1000矩阵大约需要6秒），可能比我们凡人能想出的任何东西都更优化。

它使用 Baillie-PSW素性检验的一个版本，没有已知的反例。（虽然它可能使用稍微弱一些的测试版本，有时可能会出错。也许）

- Ash Pera

Answer 10

你所写的内容是大多数普通程序员所做的，对于大部分情况来说应该已经足够了。

然而，如果你追求“最佳科学算法”，有很多变体（其确定性水平不同）在http://en.wikipedia.org/wiki/Prime_number上有记录。

例如，如果你有一个70位数字，JVM的物理限制可能会阻止你的代码运行，这时你可以使用“筛法”等方法。

再次强调，如果这是一个编程问题或软件使用的一般问题，你的代码应该是完美的 :)

- Kannan Ekanath