blocks|key|306057|text|您说您理解这一部分，但为了强调一下，生成的字符串的长度等于提供的数字。因此，当且仅当n+==+3时，该字符串有三个字符。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|306058|.?|code-block|syntax|javascript|306059|正则表达式的第一部分表示“任何字符，零次或一次”。那么基本上，是零个字符还是一个字符--或者，根据我上面提到的，是n+==+0+%7C%7C+n+==+1。如果有匹配项，则返回该匹配项的否定。这与0和1不是质数的事实相一致。|306060|(..%2B?)\\1%2B|306061|正则表达式的第二部分有点棘手，它依赖于组和反向引用。组是括号中的任何内容，然后将被正则表达式引擎捕获并存储以供以后使用。反向引用是稍后在同一正则表达式中使用的匹配组。|306062|该组捕获1个字符，然后捕获1个或多个任意字符。(%2B字符表示一个或多个，但仅限于前一个字符或组。因此，这不是“两个、四个或六个等字符”，而是“两个或三个等”。%2B？类似于%2B，但它尝试匹配尽可能少的字符。%2B通常会尝试吞噬整个字符串，这在这种情况下是不好的，因为它阻止了反向引用部分的工作。)|306063|下一部分是反向引用:相同的字符集(两个或更多)，再次出现。所述反向引用出现一次或多次。|306064|所以。捕获的组对应于捕获的自然字符数(从2开始)。然后，所述组出现一定的自然次数(也是从2开始)。如果有匹配，这意味着有可能找到两个大于或等于2的数字的乘积，这两个数字与n长度字符串匹配……这意味着你有一个复合的n。所以再一次，返回成功匹配的否定:n不是质数。|306065|如果找不到匹配，那么你就不能给出大于或等于2的两个自然数的乘积……你同时有一个非匹配和一个素数，因此再次返回匹配结果的否定。|306066|你现在看到了吗？它非常棘手(而且计算成本很高！)但是，一旦你得到它，同时也是一种简单的方式。:-)|306067|如果您有更多的问题，比如正则表达式解析是如何工作的，我可以详细说明。但我现在尽量让这个答案保持简单(或者尽可能简单)。|306068|entityMap^0|16|6|0|0|1L|G|0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|14|8|@$9|15|A|16|B|C]]|D|@]|E|$]]|$1|F|3|G|5|H|7|17|8|@]|D|@]|E|$I|J]]|$1|K|3|L|5|6|7|18|8|@$9|19|A|1A|B|C]]|D|@]|E|$]]|$1|M|3|N|5|H|7|1B|8|@]|D|@]|E|$I|J]]|$1|O|3|P|5|6|7|1C|8|@]|D|@]|E|$]]|$1|Q|3|R|5|6|7|1D|8|@]|D|@]|E|$]]|$1|S|3|T|5|6|7|1E|8|@]|D|@]|E|$]]|$1|U|3|V|5|6|7|1F|8|@]|D|@]|E|$]]|$1|W|3|X|5|6|7|1G|8|@]|D|@]|E|$]]|$1|Y|3|Z|5|6|7|1H|8|@]|D|@]|E|$]]|$1|10|3|11|5|6|7|1I|8|@]|D|@]|E|$]]|$1|12|3|-4|5|6|7|1J|8|@]|D|@]|E|$]]]|13|$]]

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 <code>n == 3</code>.

<pre><code>.?
</code></pre>

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, <code>n == 0 || n == 1</code>. If we have the match, then return the negation of that. This corresponds with the fact that zero and one are NOT prime.

<pre><code>(..+?)\\1+
</code></pre>

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.

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.

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.

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).

blocks|key|309109|text|我将在素数测试之外解释正则表达式的部分:下面的正则表达式，给定一个包含重复String+t的String+s，查找t。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|309110|++++System.out.println(
++++++++"MamamiaMamamiaMamamia".replaceAll("%5E(.*)\\1%2B$",+"$1")
++++);+//+prints+"Mamamia"|code-block|syntax|javascript|309111|它的工作方式是正则表达式将(.*)捕获到\1中，然后查看是否有\1%2B跟随它。使用%5E和$可确保匹配的必须是整个字符串。|309112|所以，在某种程度上，我们得到了String+s，它是String+t的“倍数”，正则表达式将找到这样的t+(最长的可能，因为\1是贪婪的)。|309113|一旦理解了这个正则表达式的工作原理(现在先忽略OP的正则表达式中的第一个替代)，解释它如何用于素数测试就很简单了。|309114|309115|要测试n的素性，首先生成长度为n的正则表达式(用相同的char)|unordered-list-item|309116|The+String填充)将某个长度的String+(例如k)捕获到\1中，并尝试将\1%2B与D25的其余部分进行匹配。如果存在匹配，则D28是D29的适当倍数，因此D30不是质数。如果没有匹配，则不存在分隔D34的D33因此，n是一个prime|309117|309118|​|309119|309120|309121|+.?%7C(..%2B?)\1%2B如何匹配素数？|blockquote|309122|309123|309124|实际上，不是这样的！It+matches+String的长度不是质数！|309125|309126|.?：交替的第一部分匹配长度为0或1的素数(+definition)|309127|(..%2B?)\1%2B不是素数:交替的第二部分，上面解释的正则表达式的变体，匹配长度为String的n的String是长度k+>=+2的倍数(即n是一个复合数，而不是素数)。|309128|注意，不情愿的修饰符?实际上并不是为了正确而需要的，但是它可以通过尝试更小的k+?来帮助加速这个过程|309129|309130|309131|309132|请注意return语句中的!+boolean补码运算符:它对matches求反。当正则表达式不匹配时，n是质数！这是一个双重否定的逻辑，难怪它有点令人困惑！！|309133|309134|简单化|309135|下面是代码的简单重写，使其更具可读性：|309136|public+static+boolean+isPrime(int+n)+{
++++String+lengthN+=+new+String(new+char[n]);
++++boolean+isNotPrimeN+=+lengthN.matches(".?%7C(..%2B?)\\1%2B");
++++return+!isNotPrimeN;
}|309137|上述代码本质上与原始Java代码相同，但被分成多个语句，并将这些语句赋值给局部变量，以使逻辑更易于理解。|309138|我们还可以使用有限重复来简化正则表达式，如下所示：|309139|boolean+isNotPrimeN+=+lengthN.matches(".{0,1}%7C(.{2,})\\1%2B");|309140|同样，给定一个长度为n的String，用相同的char填充，|309141|309142|.{0,1}检查n+=+0,1，而不是prime|309143|(.{2,})\1%2B检查n是否是k+>=+2的适当倍数，而不是|309144|309145|除了\1上不情愿的修饰符?+(为清楚起见省略了)之外，上面的正则表达式与原始正则表达式相同。|309146|309147|更有趣的正则表达式|309148|下面的正则表达式使用了类似的技术；它应该具有教育意义：|309149|System.out.println(
++++"OhMyGod=MyMyMyOhGodOhGodOhGod"
++++++++.replaceAll("%5E(.%2B)(.%2B)(.%2B)=(\\1%7C\\2%7C\\3)%2B$",+"$1!+$2!+$3!")
);+//+prints+"Oh!+My!+God!"|309150|另请参阅|309151|309152|Regular+expressions:+who's+greedier|309153|309154|entityMap|0|LINK|mutability|MUTABLE|url|http://java.sun.com/javase/6/docs/api/java/lang/String.html#matches%2528java.lang.String%2529|1|https://stackoverflow.com/questions/2565924/regular-expression-whos-greedier^0|11|8|1A|8|1L|1|0|0|D|4|K|2|V|3|14|1|16|1|0|F|8|Q|8|1F|1|1Q|2|0|0|0|3|1|F|1|R|4|0|4|6|J|6|T|1|Y|2|16|3|35|1|0|0|0|0|0|1|C|0|0|0|L|6|D|7|0|0|0|0|2|F|1|H|1|0|0|9|15|6|1C|1|1E|6|1N|6|1Y|1|1|A|1|12|1|14|1|1|0|0|0|3|6|D|1|F|7|U|7|1F|1|0|0|0|0|0|0|0|0|A|1|C|6|N|4|0|0|0|6|8|7|0|0|A|C|1|G|6|0|0|2|2|C|1|0|0|0|0|0|0|0|0|Z|1|0|0^^$0|@$1|2|3|4|5|6|7|2U|8|@$9|2V|A|2W|B|C]|$9|2X|A|2Y|B|C]|$9|2Z|A|30|B|C]]|D|@]|E|$]]|$1|F|3|G|5|H|7|31|8|@]|D|@]|E|$I|J]]|$1|K|3|L|5|6|7|32|8|@$9|33|A|34|B|C]|$9|35|A|36|B|C]|$9|37|A|38|B|C]|$9|39|A|3A|B|C]|$9|3B|A|3C|B|C]]|D|@]|E|$]]|$1|M|3|N|5|6|7|3D|8|@$9|3E|A|3F|B|C]|$9|3G|A|3H|B|C]|$9|3I|A|3J|B|C]|$9|3K|A|3L|B|C]]|D|@]|E|$]]|$1|O|3|P|5|6|7|3M|8|@]|D|@]|E|$]]|$1|Q|3|-4|5|6|7|3N|8|@]|D|@]|E|$]]|$1|R|3|S|5|T|7|3O|8|@$9|3P|A|3Q|B|C]|$9|3R|A|3S|B|C]|$9|3T|A|3U|B|C]]|D|@]|E|$]]|$1|U|3|V|5|T|7|3V|8|@$9|3W|A|3X|B|C]|$9|3Y|A|3Z|B|C]|$9|40|A|41|B|C]|$9|42|A|43|B|C]|$9|44|A|45|B|C]|$9|46|A|47|B|C]]|D|@]|E|$]]|$1|W|3|-4|5|6|7|48|8|@]|D|@]|E|$]]|$1|X|3|Y|5|6|7|49|8|@]|D|@]|E|$]]|$1|Z|3|-4|5|6|7|4A|8|@]|D|@]|E|$]]|$1|10|3|-4|5|6|7|4B|8|@]|D|@]|E|$]]|$1|11|3|12|5|13|7|4C|8|@$9|4D|A|4E|B|C]]|D|@]|E|$]]|$1|14|3|-4|5|6|7|4F|8|@]|D|@]|E|$]]|$1|15|3|-4|5|6|7|4G|8|@]|D|@]|E|$]]|$1|16|3|17|5|6|7|4H|8|@$9|4I|A|4J|B|C]]|D|@$9|4K|A|4L|1|4M]]|E|$]]|$1|18|3|-4|5|6|7|4N|8|@]|D|@]|E|$]]|$1|19|3|1A|5|T|7|4O|8|@$9|4P|A|4Q|B|C]|$9|4R|A|4S|B|C]|$9|4T|A|4U|B|C]]|D|@]|E|$]]|$1|1B|3|1C|5|T|7|4V|8|@$9|4W|A|4X|B|C]|$9|4Y|A|4Z|B|C]|$9|50|A|51|B|C]|$9|52|A|53|B|C]|$9|54|A|55|B|C]|$9|56|A|57|B|C]]|D|@]|E|$]]|$1|1D|3|1E|5|T|7|58|8|@$9|59|A|5A|B|C]|$9|5B|A|5C|B|C]|$9|5D|A|5E|B|C]]|D|@]|E|$]]|$1|1F|3|-4|5|6|7|5F|8|@]|D|@]|E|$]]|$1|1G|3|-4|5|6|7|5G|8|@]|D|@]|E|$]]|$1|1H|3|Y|5|6|7|5H|8|@]|D|@]|E|$]]|$1|1I|3|1J|5|6|7|5I|8|@$9|5J|A|5K|B|C]|$9|5L|A|5M|B|C]|$9|5N|A|5O|B|C]|$9|5P|A|5Q|B|C]|$9|5R|A|5S|B|C]]|D|@]|E|$]]|$1|1K|3|-4|5|6|7|5T|8|@]|D|@]|E|$]]|$1|1L|3|1M|5|6|7|5U|8|@]|D|@]|E|$]]|$1|1N|3|1O|5|6|7|5V|8|@]|D|@]|E|$]]|$1|1P|3|1Q|5|H|7|5W|8|@]|D|@]|E|$I|J]]|$1|1R|3|1S|5|6|7|5X|8|@]|D|@]|E|$]]|$1|1T|3|1U|5|6|7|5Y|8|@]|D|@]|E|$]]|$1|1V|3|1W|5|H|7|5Z|8|@]|D|@]|E|$I|J]]|$1|1X|3|1Y|5|6|7|60|8|@$9|61|A|62|B|C]|$9|63|A|64|B|C]|$9|65|A|66|B|C]]|D|@]|E|$]]|$1|1Z|3|-4|5|6|7|67|8|@]|D|@]|E|$]]|$1|20|3|21|5|T|7|68|8|@$9|69|A|6A|B|C]|$9|6B|A|6C|B|C]]|D|@]|E|$]]|$1|22|3|23|5|T|7|6D|8|@$9|6E|A|6F|B|C]|$9|6G|A|6H|B|C]|$9|6I|A|6J|B|C]]|D|@]|E|$]]|$1|24|3|-4|5|6|7|6K|8|@]|D|@]|E|$]]|$1|25|3|26|5|6|7|6L|8|@$9|6M|A|6N|B|C]|$9|6O|A|6P|B|C]]|D|@]|E|$]]|$1|27|3|-4|5|6|7|6Q|8|@]|D|@]|E|$]]|$1|28|3|29|5|6|7|6R|8|@]|D|@]|E|$]]|$1|2A|3|2B|5|6|7|6S|8|@]|D|@]|E|$]]|$1|2C|3|2D|5|H|7|6T|8|@]|D|@]|E|$I|J]]|$1|2E|3|2F|5|6|7|6U|8|@]|D|@]|E|$]]|$1|2G|3|-4|5|6|7|6V|8|@]|D|@]|E|$]]|$1|2H|3|2I|5|T|7|6W|8|@]|D|@$9|6X|A|6Y|1|6Z]]|E|$]]|$1|2J|3|-4|5|6|7|70|8|@]|D|@]|E|$]]|$1|2K|3|-4|5|6|7|71|8|@]|D|@]|E|$]]]|2L|$2M|$5|2N|2O|2P|E|$2Q|2R]]|2S|$5|2N|2O|2P|E|$2Q|2T]]]]

I will explain the regex part outside of primality testing: the following regex, given a <code>String s</code> which consists of repeating <code>String t</code>, finds <code>t</code>.

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

The way it works is that the regex captures <code>(.*)</code> into <code>\1</code>, and then sees if there's <code>\1+</code> following it. Using the <code>^</code> and <code>$</code> ensures that a match must be of the whole string.

So, in a way, we're given <code>String s</code>, which is a "multiple" of <code>String t</code>, and the regex will find such <code>t</code> (the longest possible, since <code>\1</code> is greedy).

Once you understand why this regex works, then (ignoring the first alternate in OP's regex for now) explaining how it's used for primality testing is simple.

<ul>
<li>To test primality of <code>n</code>, first generate a <code>String</code> of length <code>n</code> (filled with the same <code>char</code>)</li>
<li>The regex captures a <code>String</code> of some length (say <code>k</code>) into <code>\1</code>, and tries to match <code>\1+</code> to the rest of the <code>String</code>

<ul>
<li>If there is a match, then <code>n</code> is a proper multiple of <code>k</code>, and therefore <code>n</code> is not prime.</li>
<li>If there's no match, then no such <code>k</code> exists that divides <code>n</code>, and <code>n</code> is therefore a prime</li>
</ul></li>
</ul>

<hr>

<blockquote>
 How does <code>.?|(..+?)\1+</code> match prime numbers?
</blockquote>

Actually, it doesn't! It <a href="http://java.sun.com/javase/6/docs/api/java/lang/String.html#matches%28java.lang.String%29" rel="noreferrer">matches</a> <code>String</code> whose length is NOT prime!

<ul>
<li><code>.?</code> : The first part of the alternation matches <code>String</code> of length <code>0</code> or <code>1</code> (NOT prime by definition)</li>
<li><code>(..+?)\1+</code> : The second part of the alternation, a variation of the regex explained above, matches <code>String</code> of length <code>n</code> that is "a multiple" of a <code>String</code> of length <code>k &gt;= 2</code> (i.e. <code>n</code> is a composite, NOT a prime).

<ul>
<li>Note that the reluctant modifier <code>?</code> is actually not needed for correctness, but it may help speed up the process by trying smaller <code>k</code> first</li>
</ul></li>
</ul>

Note the <code>!</code> <code>boolean</code> complement operator in the <code>return</code> statement: it negates the <code>matches</code>. It's when the regex DOESN'T match, <code>n</code> is prime! It's a double-negative logic, so no wonder it's kind of confusing!!

<hr>

<h3>Simplification</h3>

Here's a simple rewriting of the code to make it more readable:

<pre><code>public static boolean isPrime(int n) {
 String lengthN = new String(new char[n]);
 boolean isNotPrimeN = lengthN.matches(".?|(..+?)\\1+");
 return !isNotPrimeN;
}
</code></pre>

The above is essentially the same as the original Java code, but broken apart into multiple statements with assignments to local variables to make the logic easier to understand.

We can also simplify the regex, using finite repetition, as follows:

<pre><code>boolean isNotPrimeN = lengthN.matches(".{0,1}|(.{2,})\\1+");
</code></pre>

Again, given a <code>String</code> of length <code>n</code>, filled with the same <code>char</code>,

<ul>
<li><code>.{0,1}</code> checks if <code>n = 0,1</code>, NOT prime</li>
<li><code>(.{2,})\1+</code> checks if <code>n</code> is a proper multiple of <code>k &gt;= 2</code>, NOT prime</li>
</ul>

With the exception of the reluctant modifier <code>?</code> on <code>\1</code> (omitted for clarity), the above regex is identical to the original.

<hr>

<h3>More fun regex</h3>

The following regex uses similar technique; it should be educational:

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

<h3>See also</h3>

<ul>
<li><a href="https://stackoverflow.com/questions/2565924/regular-expression-whos-greedier">Regular expressions: who's greedier</a></li>
</ul>

blocks|key|3045233|text|不错的正则表达式技巧(虽然效率很低)……:)|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3045234|正则表达式按如下方式定义非质数：|3045235|N不是素数当且仅当N<=1或N可被某个K>1整除。|3045236|不是将N的简单数字表示传递给正则表达式引擎，而是向其提供由重复字符组成的长度为N的序列。析取的第一部分使用反向引用检查N=0或N=1，第二部分使用后向引用查找除数K>1。它强制正则表达式引擎找到一些可以至少重复两次的非空子序列，以便形成序列。如果存在这样的子序列，则意味着它的长度除以N，因此N不是质数。|offset|length|style|BOLD|3045237|entityMap^0|0|0|0|10|3|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|O|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|P|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|Q|8|@$H|R|I|S|J|K]]|9|@]|A|$]]|$1|L|3|-4|5|6|7|T|8|@]|9|@]|A|$]]]|M|$]]

Nice regex trick (though very inefficient)... :)

The regex defines non-primes as follows:

N is not prime if and only if N&lt;=1 OR N is divisible by some K>1.

Instead of passing the simple digital representation of N to the regex engine, it is fed with a sequence of length N, composed of a repeating character. The first part of the disjunction checks for N=0 or N=1, and the second one looks for a divisor K>1, using backreferences. It forces the regex engine to find some non empty sub-sequence that can be repeated at least twice in order to form the sequence. If such a subsequence exists, it means that its length divides N, hence N is not prime.

blocks|key|3045263|text|/%5E1?$%7C%5E(11%2B?)\1%2B$/|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|3045264|应用于转换为基数1+(1=1，2=11，3=111，...)后的数字。非质数将与此匹配。如果不匹配，则是质数。|unstyled|3045265|解释here。|offset|length|3045266|entityMap|0|LINK|mutability|MUTABLE|url|https://stackoverflow.com/questions/3296050/how-does-this-regex-find-primes/3296068#3296068^0|0|0|2|4|0|0^^$0|@$1|2|3|4|5|6|7|S|8|@]|9|@]|A|$B|C]]|$1|D|3|E|5|F|7|T|8|@]|9|@]|A|$]]|$1|G|3|H|5|F|7|U|8|@]|9|@$I|V|J|W|1|X]]|A|$]]|$1|K|3|-4|5|F|7|Y|8|@]|9|@]|A|$]]]|L|$M|$5|N|O|P|A|$Q|R]]]]

<pre><code>/^1?$|^(11+?)\1+$/
</code></pre>

Apply to numbers after conversion to base 1 (1=1, 2=11, 3=111, ...). Non-primes will match this. If it doesn't match, it is prime.

Explanation <a href="https://stackoverflow.com/questions/3296050/how-does-this-regex-find-primes/3296068#3296068">here</a>.

I found the following code example for Java on <a href="http://rosettacode.org/wiki/Primality_by_trial_division#By_Regular_Expression" rel="noreferrer">RosettaCode</a>:

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

<ul>
<li>I don't know Java in particular but understand all aspects of this snippet except for the regex itself</li>
<li>I have basic to basic-advanced knowledge of Regex as you find it in the built-in PHP functions</li>
</ul>

How does <code>.?|(..+?)\\1+</code> match prime numbers?

How to determine if a number is a prime with regex?

Java

我在上找到了下面的Java代码示例public static boolean prime(int n) {  return !new String(new char[n]).matches(".?|(..+?)\\1+");}PHP 我不是特别了解，但我了解这段代码的所有方面，除了本身。我对regex有基本到高级的知识...

问如何用正则表达式判断一个数是否是质数？
EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问如何用正则表达式判断一个数是否是质数？EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问如何用正则表达式判断一个数是否是质数？
EN