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

我在 RosettaCode上发现了以下 Java 代码示例:

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

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

33295 次浏览
小开
最佳答案

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

.?

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

(..+?)\\1+

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

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

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

那么。捕获的组对应于捕获的自然数量的字符(从2开始)。该组然后出现一些自然的次数(也从2以后)。如果存在匹配，这意味着有可能找到两个大于或等于2的乘积来匹配 n 长度的字符串... ... 这意味着您有一个合成的 n。因此，再次返回成功匹配的否定值: n 不是质数。

如果找不到匹配项，那么你就无法得到两个自然数大于或等于2的乘积... ... 而且既有非匹配项又有质数，因此返回匹配结果的负数。

你现在看到了吗？这是令人难以置信的棘手(和计算昂贵!)但同时也很简单，一旦你明白了。:-)

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

小开

我将在素数测试之外解释正则表达式部分: 给定一个由重复 String t组成的 String s，下面的正则表达式找到 t。

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

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

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

一旦理解了这个正则表达式的工作原理，那么(暂时忽略 OP 的正则表达式中的第一个备选项)解释如何将其用于素数测试就很简单了。

  • 为了测试 n的质性，首先生成一个长度为 n的 String(用相同的 char填充)
  • 正则表达式将一个长度为 String(比如说 k)的值捕获到 \1中，并尝试将 \1+与 String的其余部分匹配起来
    • 如果有匹配，那么 n就是 k的正确倍数，因此 n不是质数。
    • 如果没有匹配，那么就不存在这样的 k除以 n，因此 n是素数

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

实际上，它没有! 它 火柴 String的长度不是质数！

  • .?: 交替的第一部分匹配长度为 0或 1的 String(定义为非质数)
  • (..+?)\1+: 交替的第二部分，上面解释的正则表达式的变体，匹配长度为 n的 String，它是长度为 k >= 2的 String的“倍数”(即 n是复合的，而不是质数)。
    • 请注意，不情愿的修饰符 ?实际上并不需要为正确性，但它可能有助于加快过程中尝试较小的 k第一

请注意 return语句中的 ! boolean补运算符: 它负 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+");

同样，给定一个长度为 n的 String，用相同的 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!"

参见

小开

不错的正则表达式技巧(尽管效率很低) ... :)

正则表达式对非质数的定义如下:

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

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

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

适用于转换为基数1(1 = 1,2 = 11,3 = 111，...)后的数字。非素数会匹配这个。如果不匹配，就是质数。

解释 给你。


提交答案