java - Java 中的 Arcane isPrime 方法

Question

考虑以下方法:

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

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

Answer 1

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

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

等等。实际上，可以使用任何字符(因此表达式中有 .)，但我将使用“1”。

其次，请注意此正则表达式匹配复合(非质数)数字；因此否定检测素数。

---

解释:

表达式的前半部分，

.?

表示字符串 ""(0) 和 "1"(1) 是匹配项，即不是质数(根据定义，though arguable。)

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

Match the shortest string whose length is at least 2, for example, "11" (2). Now, see if we can match the entire string by repeating it. Does "1111" (4) match? Does "111111" (6) match? Does "11111111" (8) match? And so on. If not, then try it again for the next shortest string, "111" (3). Etc.

现在您可以看到，如果原始字符串不能作为其子字符串的倍数 进行匹配，那么根据定义，它是质数!

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

---

效率:

这很有趣，但肯定效率不高，通过各种论据，我将在下面整合其中一些:

• 正如@TeddHopp 指出的那样，众所周知的埃拉托色尼筛法不会费心检查整数的倍数，例如 4、6 和 9，因为在检查 2 和3. 唉，这种正则表达式方法会详尽地检查每个较小的整数。

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

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

• 正如@Foon 指出的那样，存在概率方法，这些方法对于较大的数字可能更有效，尽管它们可能并不总是正确的(而是出现伪素数)。但也有 100% 准确且比基于筛选的方法更有效的确定性测试。 Wolfram's有一个很好的总结。