如何确定一个数是否是带正则数的素数?

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (23)

public static boolean prime(int n) {
  return !new String(new char[n]).matches(".?|(..+?)\\1+");
}
  • 我并不特别了解Java,但是除了正则表达式本身之外,我还了解这个片段的所有方面
  • 我对regex的基本知识有基本的了解,因为可以在内置的php函数中找到它。

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

提问于
用户回答回答于

生成的字符串的长度等于所提供的数字,字符串有三个字符当且仅当n == 3

.?

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

(..+?)\\1+

正则表达式的第二部分更复杂,依赖于组和反向引用。组是括号中的任何内容,然后由regex引擎捕获并存储,供以后使用。反向引用是后面在同一正则表达式中使用的匹配组。

该组捕获一个字符,然后捕获任意字符的一个或多个字符。(+字符是指一个或多个字符,但仅指前一个字符或组中的字符或组。所以,这不是“二、四、六等字”,而是“二、三等字”。+?类似于+,但它试图匹配尽可能少的字符。+通常会尝试吞食整个字符串,这在这种情况下是不好的,因为它阻止了反向引用部分的工作。)

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

所以。捕获的组对应于捕获的字符的自然数量(从2到2)。然后,该群体出现一些自然次数(也从2次)。如果有匹配,这就意味着有可能找到一个大于或等于2的乘积,它与n长字符串相匹配,意味着你有一个复合n。因此,再次返回成功匹配的否定:n不是素数。

如果找不到匹配,那么你就不能得到一个两个自然数大于等于2的乘积,而且你有一个不匹配和一个素数,因此再次返回了匹配结果的否定。

用户回答回答于

我将在素数测试之外解释regex部分:下面的regex给出了String s其中包括重复String t,发现t

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

它的工作方式是regex捕获(.*)\1,然后看看是否有\1+跟着它。使用^$确保匹配必须是整个字符串。

所以,在某种程度上,我们String s的“倍数”。String t,大王会发现t(尽可能最长的,因为\1是贪婪的)。

一旦您理解了这个正则表达式的工作原理,那么(暂时忽略OP正则表达式中的第一个替代方案),解释它是如何用于原始性测试是很简单的。

  • 检验原始性n,首先生成一个String长度n(充满相同的char)
  • 正则表达式捕获String长度(例如)k)进入\1,并试图匹配\1+其他的String
    • 如果有匹配,那么n的适当倍数k,因此n不是素数。
    • 如果没有匹配,那么就没有这样的k存在分裂n,和n因此是素数

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

事实上,没有!String它的长度不是素数!

  • .?*交替比赛的第一部分String长度01(定义为非素数)
  • (..+?)\1+*第二部分的交替,是上述解释的正则表达式的一个变体,与之相匹配。String长度n的“倍数”。String长度k >= 2(即:n是一个合成的,而不是一个质数)。
    • 注意,不情愿的修饰符?实际上并不需要正确性,但它可能有助于通过尝试更小的方法来加快进程。k第一

注意!boolean补码运算符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+");

再一次,给出String长度n,充满了同样的东西char

  • .{0,1}检查n = 0,1,不是素数
  • (.{2,})\1+检查n的适当倍数k >= 2,不是素数

更有趣的正则表达式

下面的regex使用类似的技术;它应该具有教育性:

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

扫码关注云+社区