这个正则表达式如何找到质数？

Question

86

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

这个页面声称这个正则表达式可以发现非质数（通过反例：质数）：

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

这如何找到质数？

- Dinah

15

这不是重复。它使用了不同的正则表达式和技巧，并且有更好的答案。 - bmargulies

4

这是个重复问题。考虑到此问题的输入限制以及Java的String.matches方法会将正则表达式与整个字符串进行匹配（因此^和$被隐含在内），所以正则表达式是一样的。 - Roger Pate

1

@Rog - 那里被点赞的答案从未提到一元运算符。 - bmargulies

如果您认为自己能够提供更好或更完整的答案，请尽管发表。我会标记此问题以进行合并，但是问题文本中的表面差异意味着答案需要进行一些编辑（通常情况下都是如此），即使在删除这些表面差异后，问题是相同的。 - Roger Pate

@Rog，此时此刻我只会相信钻石能够巧妙地合并。 - bmargulies

^(?!1?$|(11+?)\1+$)1+$ 这个正则表达式可以找到实际的质数，它使用了负向前瞻。 - Wilson

1个回答

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

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

- Matchu · Accepted Answer

我觉得这篇文章讲解得相当清楚，但我也会尝试解释一下。

输入以“一元”形式表示。1为1，2为11，3为111，以此类推。零是一个空字符串。

正则表达式的第一部分将0和1视为非质数。接下来，神奇的事情发生在第二部分。

(11+?)开始寻找除数。它首先定义为11，即2。\1是指之前捕获的匹配项，因此\1+判断数字是否可以被该除数整除。（例如111111将变量分配为11，然后确定剩余的1111是11重复，因此6可以被2整除。）

如果数字不能被2整除，正则表达式引擎会增加除数。 (11+?)变成111，我们再次尝试。如果在任何时候正则表达式匹配成功，则该数字具有可产生无余数的除数，因此该数字不是质数。