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

Question

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

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

• 我特别不了解Java,但除了正则表达式本身之外,还要理解这个片段的所有方面
• 当你在内置的PHP函数中找到它时,我有基本的高级Regex知识

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

Answer 1

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

.?

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

(..+?)\\1+

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

该组捕获1个字符,然后捕获任何字符中的1个或多个字符.(+字符表示一个或多个,但仅限于前一个字符或组.所以这不是"两个或四个或六个等字符",而是"两个或三个等".+？是+,但是它试图匹配尽可能少的字符.+如果可以的话,通常会尝试吞噬整个字符串,这在这种情况下很糟糕,因为它会阻止反向引用部分工作.)

下一部分是反向引用:同一组字符(两个或更多)再次出现.所述反向引用出现一次或多次.

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

如果没有匹配,可以发现,那么你就不能拿出你的两个自然数大于或等于2的产品......你有两个不匹配和优越的,否定的,因此再次返回匹配结果.

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

如果你有进一步的问题,我可以详细说明,比如正则表达式解析实际上是如何工作的.但我现在试图让这个答案变得简单(或者尽可能简单).

Answer 2

我将在素性测试之外解释正则表达式部分:下面的正则表达式,给出一个String s由重复String t,发现组成的部分t.

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

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

所以,在某种程度上,我们被给予String s,这是一个"倍数" String t,正则表达式将找到这样的t(最长的,因为\1是贪婪的).

一旦你理解了这个正则表达式的工作原理,那么(暂时忽略OP正则表达式中的第一个替代)解释它如何用于素性测试很简单.

• 为了测试素数n,首先生成一个String长度n(填充相同char)
• 正则表达式捕获了String一些长度(比如说k)\1,并尝试匹配\1+其余部分String
  • 如果有匹配,则n是正确的倍数k,因此n不是素数.
  • 如果没有匹配,那么就没有这样的k分裂n,n因此是一个素数

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

实际上,它没有!它匹配 String的长度不是素数!

• .?:交替的第一部分匹配String长度0或1(根据定义不是素数)
• (..+?)\1+:交替的第二部分,该正则表达式的变形例如上所述,匹配String长度的n是一个"倍数" String长度的k >= 2(即n是一个复合物,不是素).
  • 请注意,不愿意修改?实际上是没有必要的正确性,但它可以帮助加快这一进程,试图通过更小的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,而不是素数

与不愿改性剂的异常?上\1(为清楚起见省略),上述正则表达式是相同的原件.

更有趣的正则表达式

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

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

也可以看看

• 正则表达式:谁更贪婪

Answer 3

很好的正则表达技巧(虽然非常低效)... :)

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

当且仅当N <= 1或N被某些K> 1整除时,N不是素数.

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