134

我在RosettaCode上找到了以下 Java 代码示例：

public static boolean prime(int n) {
  return !new String(new char[n]).matches(".?|(..+?)\\1+");
}
  • 我不特别了解 Java，但了解此代码段的所有方面，除了正则表达式本身
  • 正如您在内置 PHP 函数中找到的那样，我对 Regex 具有基本到基础的高级知识

如何.?|(..+?)\\1+匹配素数？

4

4 回答 4

121

您说您了解这部分，但只是强调一下，生成的字符串的长度等于提供的数字。所以字符串有三个字符当且仅当n == 3。

.?

正则表达式的第一部分说，“任何字符，零次或一次”。所以基本上，有零个或一个字符 - 或者，根据我上面提到的，n == 0 || n == 1. 如果我们有匹配，则返回否定。这与零和一不是素数的事实相对应。

(..+?)\\1+

正则表达式的第二部分有点棘手，依赖于组和反向引用。组是括号中的任何内容，然后将由正则表达式引擎捕获并存储以供以后使用。反向引用是稍后在同一正则表达式中使用的匹配组。

该组捕获 1 个字符，然后捕获 1 个或多个任意字符。（+ 字符表示一个或多个，但仅表示前一个字符或组。所以这不是“两个或四个或六个等字符”，而是“两个或三个等”。+？就像 +，但是它会尝试匹配尽可能少的字符。+ 通常会尝试吞噬整个字符串，如果可以的话，这在这种情况下很糟糕，因为它会阻止反向引用部分工作。）

下一部分是反向引用：同一组字符（两个或更多）再次出现。所述反向引用出现一次或多次。

所以。捕获的组对应于捕获的自然数量的字符（从 2 个开始）。然后所述组出现一些自然次数（也从 2 次开始）。如果存在匹配项，则这意味着可以找到两个大于或等于 2 的数字的乘积与 n 长度的字符串匹配……这意味着您有一个复合 n。因此，再次返回对成功匹配的否定：n 不是素数。

如果找不到匹配项，那么您将无法得出两个大于或等于 2 的自然数的乘积……并且您同时拥有不匹配项和质数，因此再次返回否定的比赛结果。

你现在看到了吗？这是令人难以置信的棘手（而且计算成本很高！）但同时它也很简单，一旦你得到它。:-)

如果您还有其他问题，我可以详细说明，例如正则表达式解析的实际工作原理。但我现在试图让这个答案保持简单（或者尽可能简单）。

于 2010-05-08T18:10:44.640 回答
73

我将解释素性测试之外的正则表达式部分：以下正则表达式，给定String s由 repeating 组成的a String t， find t。

    System.out.println(
        "MamamiaMamamiaMamamia".replaceAll("^(.*)\\1+$", "$1")
    ); // prints "Mamamia"

它的工作方式是正则表达式捕获(.*)到\1，然后查看是否有\1+跟随它。使用^and$确保匹配必须是整个字符串。

因此，在某种程度上，我们得到了String s，它是 的“倍数” String t，并且正则表达式会找到这样t的（最长的可能，因为\1它是贪婪的）。

一旦你理解了这个正则表达式为什么起作用，那么（暂时忽略 OP 正则表达式中的第一个替代）解释它如何用于素数测试就很简单了。

  • 要测试 的素数n，首先生成一个String长度n（填充相同的char）
  • String正则表达式将某个长度（例如k）的 a 捕获到 中\1，并尝试\1+匹配String
    • 如果匹配，则n是 的真倍数k，因此n不是素数。
    • 如果没有匹配，则不k存在可除n的，n因此是素数

如何.?|(..+?)\1+匹配素数？

其实不然！它匹配 String长度不是素数的！

  • .?: 交替匹配的第一部分String长度0或1（根据定义不是素数）
  • (..+?)\1+：交替的第二部分，上面解释的正则表达式的变体，匹配String长度n为 a 的“倍数”的String长度k >= 2（即n复合，不是素数）。
    • 请注意，relucant 修饰符实际上不是正确性所必需的，但它可能有助于通过先?尝试更小来加快过程k

注意语句! boolean中的补码运算符return：它否定matches. 当正则表达式不匹配时，n它是素数！这是一个双重否定的逻辑，所以难怪它有点令人困惑！

简化

这是对代码的简单重写以使其更具可读性：

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

上面的代码与原始的 Java 代码基本相同，但分解为多个语句，并分配给局部变量以使逻辑更易于理解。

我们还可以使用有限重复来简化正则表达式，如下所示：

boolean isNotPrimeN = lengthN.matches(".{0,1}|(.{2,})\\1+");

再次，给定一个String长度n，填充相同char，

  • .{0,1}检查是否n = 0,1，不是素数
  • (.{2,})\1+检查是否n是 的正确倍数k >= 2，而不是素数

除了不情愿的修饰符?on \1（为清楚起见省略），上述正则表达式与原始表达式相同。

更有趣的正则表达式

以下正则表达式使用类似的技术；它应该具有教育意义：

System.out.println(
    "OhMyGod=MyMyMyOhGodOhGodOhGod"
        .replaceAll("^(.+)(.+)(.+)=(\\1|\\2|\\3)+$", "$1! $2! $3!")
); // prints "Oh! My! God!"

也可以看看

于 2010-05-08T18:19:23.790 回答
27

不错的正则表达式技巧（虽然效率很低）... :)

正则表达式定义非素数如下：

N 不是素数当且仅当 N<=1 或 N 可被某个 K>1 整除。

不是将 N 的简单数字表示传递给正则表达式引擎，而是输入一个长度为N 的序列，由一个重复字符组成。析取的第一部分检查 N=0 或 N=1，第二部分使用反向引用查找除数 K>1。它强制正则表达式引擎找到一些可以重复至少两次以形成序列的非空子序列。如果存在这样的子序列，则意味着它的长度除以 N，因此 N 不是素数。

于 2010-05-08T18:48:10.207 回答
2 
/^1?$|^(11+?)\1+$/

转换为基数 1 后应用于数字（1=1, 2=11, 3=111, ...）。非素数将匹配此。如果不匹配，则为素数。

在这里解释。

于 2010-07-21T17:21:20.300 回答