10

考虑以下方法：

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

我从来都不是正则表达式大师，所以任何人都可以完全解释这种方法实际上是如何工作的吗？此外，与确定整数是否为素数的其他可能方法相比，它是否有效？

4

3 回答 3

10

首先，请注意，此正则表达式适用于一元计数系统中表示的数字，即

1       is 1
11      is 2
111     is 3
1111    is 4
11111   is 5
111111  is 6
1111111 is 7

等等。实际上，可以使用任何字符（因此.表达式中的 s），但我将使用“1”。

其次，注意这个正则表达式匹配复合（非素数）数字；因此，否定检测素性。

解释：

表达式的前半部分，

.?

表示字符串 "" (0) 和 "1" (1) 是匹配的，即不是素数（根据定义，尽管可以争论。）

后半部分用简单的英语说：

匹配长度至少为 2 的最短字符串，例如 "11" (2)。现在，看看我们是否可以通过重复来匹配整个字符串。“1111”（4）匹配吗？“111111”(6) 匹配吗？“11111111”(8) 匹配吗？等等。如果不是，则再次尝试下一个最短的字符串“111”(3)。等等。

您现在可以看到，如果原始字符串不能与其子字符串的倍数匹配，那么根据定义，它是素数！

顺便说一句，非贪婪运算符?是使“算法”从最短开始并向上计数的原因。

效率：

通过各种论点，这很有趣，但肯定不是有效的，其中一些我将在下面进行合并：

  • 正如@TeddHopp 所指出的，众所周知的埃拉托色尼筛法不会费心检查整数的倍数，例如 4、6 和 9，在检查 2 和 3 的倍数时已经“访问过”。唉，这个正则表达式方法详尽地检查每个较小的整数。

  • 正如@PetarMinchev 指出的那样，一旦我们达到数字的平方根，我们就可以“短路”多重检查方案。我们应该能够，因为大于平方根的因子必须与小于平方根的因子配对（否则两个大于平方根的因子会产生大于数字的乘积），如果存在这个更大的因子，那么我们应该已经遇到（并因此匹配）较小的因素。

  • 正如@Jesper 和@Brian 简明扼要地指出的那样，从非算法的角度来看，考虑正则表达式如何通过分配内存来存储 string开始，例如 char[9000]9000。嗯，这很容易，不是吗？;)

  • 正如@Foon 所指出的，存在概率方法可能对更大的数字更有效，尽管它们可能并不总是正确的（改为使用伪素数）。但也有确定性测试 100% 准确，并且比基于筛分的方法更有效。Wolfram's有一个很好的总结。

于 2012-10-03T19:57:08.227 回答
5

素数的一元特征以及它为什么起作用已经被讨论过了。所以这是一个使用传统方法和这种方法的测试：

public class Main {

    public static void main(String[] args) {
        long time = System.nanoTime();
        for (int i = 2; i < 10000; i++) {
            isPrimeOld(i);
        }
        time = System.nanoTime() - time;
        System.out.println(time + " ns (" + time / 1000000 + " ms)");
        time = System.nanoTime();
        for (int i = 2; i < 10000; i++) {
            isPrimeRegex(i);
        }
        time = System.nanoTime() - time;
        System.out.println(time + " ns (" + time / 1000000 + " ms)");
        System.out.println("Done");
    }

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

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

这个测试从 2 开始计算这个数字是否是 9,999 的素数。下面是它在相对强大的服务器上的输出：

8537795 ns (8 ms)
30842526146 ns (30842 ms)
Done

因此，一旦数字变得足够大，它的效率就会非常低。（对于高达 999，正则表达式的运行时间约为 400 毫秒。）对于小数字，它很快，但以传统方式生成高达 9,999 的素数仍然比以旧方式生成高达 99 的素数更快（ 23 毫秒）。

于 2012-10-03T20:05:42.423 回答
2

这不是检查数字是否为素数的真正有效方法（它检查每个除数）。

一种有效的方法是检查除数高达sqrt(number). 这是如果你想确定一个数字是否是素数。否则，有更快的概率素性检查，但不是 100% 正确。

于 2012-10-03T19:51:04.100 回答