如何确定一个数是否是正则expression式的一个主要元素？

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

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

• 我不特别了解Java，但了解这个片段的所有方面，除了正则expression式本身
• 当你在内置的PHP函数中find正则expression式时，我有基本的高级正则expression式知识

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

Answer 1

你说你理解这个部分，但只是强调，生成的string的长度等于提供的数量。 所以当且仅当n == 3 ，string有三个字符。

 .? 

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

 (..+?)\\1+ 

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

该组捕获1个字符，然后捕获1个或更多的任何字符。 （+字符是指一个或多个字符，而不是前面的字符或组，所以这不是“两个或四个或六个字符”，而是“两个或三个”。+ +是+，但它会尽量匹配尽可能less的字符，如果可能，+通常会尝试吞噬整个string，这在这种情况下是不好的，因为它阻止了反向引用部分的工作。

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

所以。 捕获的组对应于捕获的自然数字（从2开始）。 所述组然后出现一些自然次数（也从2起）。 如果有一个匹配，这意味着有可能find两个大于或等于2的数字匹配n长度string的乘积…意味着你有一个复合n。 所以再次回到成功匹配的否定：n不是素数。

如果不能find匹配，那么你不能拿出你的两个自然数大于或等于2的乘积，而且你有一个不匹配和一个素数，所以再次返回否定的比赛结果。

你现在看到了吗？ 这是令人难以置信的棘手的问题（而且计算起来也很昂贵！），但是一旦你得到它，它也同样简单。 🙂

我可以详细说明是否还有其他问题，比如说正则expression式parsing是如何工作的。 但是我现在试图保持这个答案简单（或者尽可能简单）。

Answer 2

我将解释素数testing之外的正则expression式部分：下面的正则expression式，给定一个由重复String t组成的String t ，findt 。

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

它的工作方式是正则expression式将(.*)捕获到\1 ，然后看看它是否有\1+ 。 使用^和$确保匹配必须是整个string。

所以，在某种程度上，我们得到了String s ，它是String t一个“倍数”，正则expression式会find这样的t （尽可能最长，因为\1是贪婪的）。

一旦你明白为什么这个正则expression式起作用，那么（现在忽略OP的正则expression式中的第一个替代）解释了它如何用于素性testing是很简单的。

• 为了testingn素数，首先生成一个长度为n的String （用相同的char填充）
• 正则expression式将一个长度为\1的String （如k ）捕获到\1 ，并尝试将\1+与String的其余部分匹配
  • 如果匹配，那么n是k的正确倍数，因此n不是素数。
  • 如果没有匹配，那么就不存在将n分开的k ，因此n是素数

---

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

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

• .? ：交替的第一部分匹配长度为0或1 String （NOT按定义）
• (..+?)\1+ ：交替的第二部分，上面解释的正则expression式的变体匹配长度为n的String ，该长度是长度为k >= 2的String的“倍数”（即， n是复合，不是素数）。
  • 请注意，勉强修饰符? 实际上并不需要正确性，但是可以通过首先尝试较小的k加快处理速度

注意! return语句中的boolean互补运算符：它否定matches 。 这是正则expression式不匹配时， n是素数！ 这是一个双重否定的逻辑，所以难怪这是一种混乱！

---

简单化

这是一个简单的代码重写，使其更具可读性：

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

上面基本上和原始的Java代码一样，但是分解成多个语句，赋值给局部variables，使逻辑更容易理解。

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

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

同样，给定一个长度为n的String ，填充相同的char ，

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

除了勉强的修饰词? 在\1 （为了清楚起见省略），上面的正则expression式与原来的相同。

---

更有趣的正则expression式

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

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

也可以看看

• 正则expression式：谁是贪婪的

Answer 3

很好的正则expression式技巧（虽然非常低效）… 🙂

正则expression式定义非素数如下：

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

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

Answer 4

 /^1?$|^(11+?)\1+$/ 

应用于转换后的数字为1（1 = 1，2 = 11，3 = 111，…）。 非素数将匹配这个。 如果不匹配，那就是素数。

这里解释。