如何使用正则表达式确定一个数字是否为质数？

Question

如何使用正则表达式确定一个数字是否为质数？

137

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

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

我不熟悉Java，但是理解这段代码片段除了正则表达式之外的所有方面
我有基本到基本高级的正则表达式知识，如内置的PHP函数中所使用的

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

- kitlite

9

!new String(new char[n]).matches(".?|(..+?)\\1+") 等价于 !((new String(new char[n])).matches(".?|(..+?)\\1+"))。 - Gumbo

16

这不仅计算成本高，而且可能会消耗大量的内存资源。如果有人选择使用这种方法，我建议不要这样做，因为找质数的算法非常简单（为什么要使它变得如此复杂和浪费资源）。在“new char [n]”之前应该进行检查，以确保其低于合理的阈值。例如，调用“prime(Integer.MAX_VALUE)”然后在它抛出OutOfMemoryError时报告错误。 - nicerobot

32

放轻松？ - Cam

10

@nicerobot：实际上，我撤回之前的说法。我原本认为这个问题的学术性质意味着它只用于学习目的，并且你是在表现得傲慢和愚蠢。但是仔细想过后发现并非如此；问题中从未提到或暗示正则表达式仅用于学习目的。事实上，我的第一印象是，作为代码片段，它看起来非常简单，因此初学者可能确实会认为它可以用于实践。点赞。 - Cam

9

没问题，我可以理解你为什么会这样想。我只是想提醒使用它的后果，而不是阻止学习它的工作原理。如果在我的评论中加上一个简单的“请不要部署这个”，可能会使得从你最初的角度来看，听起来不那么居高临下。 - nicerobot

显示剩余5条评论

4个回答

73

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

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

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

因此，在某种程度上，我们得到一个"多个"的String t，而正则表达式将找到这样的t（由于\1是贪婪的，所以是尽可能长的）。

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

要测试n的素性，首先生成一个长度为n的String（填充相同的char）。

正则表达式将一个长度为k的String捕获到\1中，并尝试将\1+与其余的String匹配。

如果有匹配，则n是k的适当倍数，因此n不是素数。

如果没有匹配，则不存在除n外的这样的k，因此n是素数。

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

实际上，它不能！它匹配非质数长度的String！

.?：备选项的第一部分匹配长度为0或1的String（根据定义不是质数）
(..+?)\1+：备选项的第二部分是正则表达式上面解释过的一个变体，它匹配长度为n的String，该String是长度为k>=2的String的“倍数”（即，n是合成数，不是质数）。
- 请注意，勉强的修改器?实际上不是必要的，但通过首先尝试较小的k可能有助于加速过程

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

如果给出一个长度为n的字符串，其中填充了相同的字符，

.{0,1}检查n=0,1，不是质数
(.{2,})\1+检查n是否为k>=2的proper multiple，不是质数

除了对\1使用勉强的修改符号?（为了清晰起见而省略），以上正则表达式与原始表达式完全相同。

更有趣的正则表达式

下面的正则表达式使用类似的技巧；它应该是教育性的：

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

参见

正则表达式：谁更贪婪

- polygenelubricants

6

我认为你的方法可能比我的更好。不知道为什么我会得到那么多赞和勾选标记...我认为你更应该得到它。:-( 抱歉。 - Platinum Azure

@Platinum：哇，我从没想过你会公开说出这样的话！谢谢你的支持。也许有一天我会因此得到一个“[民粹主义者]”。 - polygenelubricants

2

嗯，这只是我所感知到的真相……并不是什么大不了的事情。我来这里不是为了声望（尽管它总是一个额外的惊喜），而是为了在我能回答问题时尝试回答问题。因此，当有人在某个问题上做得比我更好时，我承认这一点也就不足为奇了。 - Platinum Azure

27

很不错的正则表达式技巧（尽管非常低效）... :)

该正则表达式将非质数定义为：

N 不是质数当且仅当 N<=1 或 N 可以被某个大于 1 的数 K 整除。

与其将 N 的简单数字表示传递给正则表达式引擎，更好的方法是使用一个由重复字符组成的长度为 N 的序列。第一部分检查 N 是否等于 0 或 1，第二部分使用反向引用寻找除数 K>1，强制正则表达式引擎查找某个非空子序列，它可以至少重复两次来形成整个序列。如果这样的子序列存在，则意味着该子序列的长度能够整除 N，因此 N 不是质数。

- Eyal Schneider

4

有趣的是，即使我反复阅读了其他更长、更技术性的解释，我发现这个解释才是让我恍然大悟的。 - Eight-Bit Guru

2

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

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

解释在这里。

- Dinah

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Platinum Azure · Accepted Answer

您说您理解这部分内容，但是为了强调一下，生成的字符串长度等于提供的数字。因此，当且仅当n == 3时，该字符串具有三个字符。

.?

正则表达式的第一部分表示“任何字符，出现零或一次”。因此，基本上是有零个或一个字符-- 或者按照我上面提到的，n == 0 || n == 1。如果我们有匹配，则返回其否定。这与零和一不是质数的事实相对应。

(..+?)\\1+

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

该分组捕获一个字符，然后是一个或多个任意字符。(加号+表示一个或多个，但仅限于前面的字符或分组。因此这不是“两个或四个或六个等字符”，而是“两个或三个等”。加号+？与+类似，但会尝试匹配尽可能少的字符。通常，加号+会尽最大可能地匹配整个字符串，这在此情况下是不好的，因为它会阻止反向引用的工作方式。)

下一部分是反向引用：同一组字符(两个或更多)，再次出现。该反向引用出现一次或多次。

所以，捕获的分组对应于捕获的自然数字符(从2开始)。然后，该组会出现某个自然数次数(也从2开始)。如果有匹配，则意味着可以找到两个大于或等于2的数字的乘积，其匹配n长度的字符串...这意味着您有一个合成的n。因此，再次返回成功匹配的否定：n不是质数。

如果找不到匹配，则无法得出大于或等于2的两个自然数的乘积...并且您既没有匹配也没有质数，因此再次返回匹配结果的否定。

现在看到了吗？它难以置信地棘手(而且计算代价昂贵!)，但是一旦你理解了它，它又有点简单。:-)

如果您有进一步的问题，比如有关正则表达式解析实际工作方式的问题，我可以进行详细说明。但是我现在正在尝试让这个答案尽可能简单(或者说尽可能简单)。