首页 文章

如何确定一个数字是否是正则表达式的素数？

提问于
浏览 次
121

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

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

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

  • 当你在内置的PHP函数中找到它时，我有基本的高级Regex知识

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

java regex primes

4 回答

  • 69

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

    .?

    正则表达式的第一部分说，"any character, zero or one times" . 所以基本上，是否有零个或一个字符 - 或者，根据我上面提到的， n == 0 || n == 1 . 如果我们有匹配，那么返回否定 . 这与零和一不是素数的事实相对应 .

    (..+?)\\1+

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

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

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

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

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

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

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

    回复于
  • 3

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

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

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

    所以，在某种程度上，我们给了 String s ，这是"multiple"的"multiple"，正则表达式会找到这样的 t （最长的，因为 \1 是贪婪的） .

    一旦你理解了这个正则表达式的工作原理，那么（忽略OP的正则表达式中的第一个替代）解释它如何用于素性测试很简单 .

    • 要测试 n 的素数，首先生成长度为 n 的 String （填充相同的 char ）

    • 正则表达式将 String 的某个长度（例如 k ）捕获到 \1 中，并尝试将 \1+ 与 String 的其余部分匹配

    • 如果匹配，则 n 是 k 的正确倍数，因此 n 不是素数 .

    • 如果没有匹配，那么就没有这样的 k 来划分 n ，因此 n 是一个素数

    怎么做？|（..？）\ 1匹配素数？

    实际上，它没有！它matches String 其长度不是素数！

    • .? ：交替的第一部分匹配 String 长度 0 或 1 （根据定义不是素数）

    • (..+?)\1+ ：交替的第二部分，上面解释的正则表达式的变体，匹配 String 长度为 n ，"a multiple"长度为 String k >= 2 （即 n 是复合，不是素数） .

    • 请注意，实际上不需要不情愿的修饰符 ? ，但它可能有助于通过首先尝试更小的 k 来加速该过程

    注意 return 语句中的 ! boolean 补码运算符：它否定了 matches . 当正则表达式不匹配时， n 是素数！它's a double-negative logic, so no wonder it'有点令人困惑!!

    简化

    这是对代码的简单重写，使其更具可读性：

    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 的正确倍数，不是素数

    除了 \1 上的不情愿修改器 ? （为清晰起见省略），上述正则表达式与原始版本相同 .

    更有趣的正则表达式

    以下正则表达式使用类似的技术;它应该具有教育意义：

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

    另见

    回复于
  • 111

    很好的正则表达技巧（虽然非常低效）... :)

    正则表达式定义非素数如下：

    当且仅当N <= 1或N被某些K> 1整除时，N才是素数 .

    它不是将N的简单数字表示传递给正则表达式引擎，而是由一个由重复字符组成的序列 length N . 析取的第一部分检查N = 0或N = 1，第二部分使用反向引用来寻找除数K> 1 . 它强制正则表达式引擎找到一些非空子序列，该子序列可以重复至少两次以形成序列 . 如果存在这样的子序列，则意味着其长度除以N，因此N不是素数 .

    回复于
  • 24
    /^1?$|^(11+?)\1+$/

    转换为基数1后应用于数字（1 = 1,2 = 11,3 = 111，...） . 非素数将与此匹配 . 如果它不匹配，那就是素数 .

    说明here .

    回复于

相关问题