如何确定一个数字是否是正则表达式的素数？ [英] How to determine if a number is a prime with regex?

问题描述

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

I found the following code example for Java on RosettaCode:

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

• 我特别不了解Java但是理解除了正则表达式本身之外的这个片段的所有方面


• 我在内置PHP函数中找到了基本的高级Regex知识



如何。？|（.. +？）\\1 + 匹配素数？

推荐答案

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

You said you understand this part, but just to emphasize, the String generated has a length equal to the number supplied. So the string has three characters if and only if n == 3.

.?

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

The first part of the regex says, "any character, zero or one times". So basically, is there zero or one character-- or, per what I mentioned above, n == 0 || n == 1. If we have the match, then return the negation of that. This corresponds with the fact that zero and one are NOT prime.

(..+?)\\1+

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

The second part of the regex is a little trickier, relying on groups and backreferences. A group is anything in parentheses, which will then be captured and stored by the regex engine for later use. A backreference is a matched group that is used later on in the same regex.

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

The group captures 1 character, then 1 or more of any character. (The + character means one or more, but ONLY of the previous character or group. So this is not "two or four or six etc. characters", but rather "two or three etc." The +? is like +, but it tries to match as few characters as possible. + normally tries to gobble the whole string if it can, which is bad in this case because it prevents the backreference part from working.)

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

The next part is the backreference: That same set of characters (two or more), appearing again. Said backreference appears one or more times.

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

So. The captured group corresponds to a natural number of characters (from 2 onward) captured. Said group then appears some natural number of times (also from 2 onward). If there IS a match, this implies that it's possible to find a product of two numbers greater than or equal to 2 that match the n-length string... meaning you have a composite n. So again, return the negation of the successful match: n is NOT prime.

如果找不到匹配，那么你就不能想出你的产品两个大于或等于2的自然数...并且你有一个不匹配和一个素数，因此再次返回否定匹配结果。

If no match can be found, then you can't come up with a your product of two natural numbers greater than or equal to 2... and you have both a non-match and a prime, hence again the returning of the negation of the match result.

你现在看到了吗？这是令人难以置信的棘手（并且计算成本很高！）但是一旦你得到它，它同时也很简单。 ： - ）

Do you see it now? It's unbelievably tricky (and computationally expensive!) but it's also kind of simple at the same time, once you get it. :-)

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

I can elaborate if you have further questions, like on how regex parsing actually works. But I'm trying to keep this answer simple for now (or as simple as it can ever be).

这篇关于如何确定一个数字是否是正则表达式的素数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！