Java中的Arcane isPrime方法

皮承基

2023-03-14

问题内容：

请考虑以下方法：

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

我从来都不是正则表达式专家，所以谁能完全解释这种方法的实际工作原理？此外，与确定整数是否为质数的其他可能方法相比，它是否有效？

问题答案：

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

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简洁地指出的那样，从非算法的角度来看，考虑正则表达式如何通过 分配内存来存储字符串 （例如 char[9000] 9000）来开始。那么，这很容易，不是吗？;）
正如@Foon所指出的那样，存在一些概率方法，对于较大的数字，可能会更有效，尽管它们可能并不总是正确的（取而代之的是伪素数）。但是，也有确定性测试100％准确，并且比基于筛子的方法效率更高。Wolfram的总结很不错。