如何确定一个数字是否是正则表达式的素数？

你说你理解这部分，但只是为了强调，生成的字符串的长度等于提供的数字。因此，该字符串有三个字符，当且仅当 .n == 3

.?

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

(..+?)\\1+

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

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

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

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

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

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

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

我将解释正则表达式部分之外的素数测试：以下正则表达式，给定一个由重复组成的正则表达式，发现 。String sString tt

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

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

所以，在某种程度上，我们被赋予了 ，这是 的“倍数”，正则表达式会找到这样的（最长的可能，因为是贪婪的）。String sString tt\1

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

• 要测试 的素数，首先生成一个长度（填充相同的nStringnchar)
• 正则表达式将一定长度（比如）的 a 捕获到 中，并尝试与其余部分匹配Stringk\1\1+String
  • 如果存在匹配项，则 是 的真倍数，因此不是素数。nkn
  • 如果没有匹配，则不存在除以 的匹配，因此是素数knn

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

实际上，事实并非如此！它匹配谁的长度不是素数！String

• .?：交替的第一部分与长度匹配或（根据定义不是素数）String01
• (..+?)\1+：交替的第二部分，上面解释的正则表达式的变体，匹配的长度是长度的“倍数”（即 是一个复合体，而不是素数）。StringnStringk >= 2n
  • 请注意，不情愿的修饰符实际上不是正确性所必需的，但它可以通过首先尝试较小的修饰符来帮助加快该过程?k

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

简单化

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

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

同样，给定一个长度，填充相同的，Stringnchar

• .{0,1}检查是否为 ，而不是素数n = 0,1
• (.{2,})\1+检查是否为 的适当倍数，而不是素数nk >= 2

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

更多有趣的正则表达式

以下正则表达式使用类似的技术;它应该是教育性的：

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

另请参见

• 正则表达式：谁更贪婪